Implement binary search algorithm in Dart. Include both iterative and recursive versions. What are the prerequisites for using binary search?

Overview

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the remaining elements in each step.

Binary search is fundamental to computer science and is 100x faster than linear search for large datasets. Understanding binary search is essential for technical interviews and forms the basis for many advanced algorithms.

Key Characteristics:

• Requires sorted data (critical prerequisite!)
• O(log n) time complexity - extremely fast
• Divide and conquer strategy
• Can be implemented iteratively or recursively

Real-world applications:

• Searching in databases with indexed columns
• Finding elements in sorted collections
• Dictionary/phone book lookups
• Version control systems (git bisect)
• Gaming (guess the number)

Prerequisites

CRITICAL REQUIREMENT: Array MUST be sorted!

dartCopy
// ✅ Can use binary search
List<int> sorted = [1, 3, 5, 7, 9, 11, 13];

// ❌ Cannot use binary search - will give wrong results!
List<int> unsorted = [5, 2, 9, 1, 7];

If unsorted:

1. Sort first:
   textCopy

   arr.sort()

   - O(n log n)
2. Then binary search - O(log n)
3. Total: O(n log n) - still better than O(n²)

Algorithm Explanation

How Binary Search Works:

1. Set left pointer to start, right pointer to end
2. Calculate middle index:
   textCopy

   mid = (left + right) ~/ 2

3. Compare middle element with target:
   • If equal → Found! Return index
   • If target < middle → Search left half
   • If target > middle → Search right half
4. Repeat until found or left > right

Visual Example:

textCopy
Find 7 in [1, 3, 5, 7, 9, 11, 13]

Step 1: [1, 3, 5, |7|, 9, 11, 13]  mid=7, found!

Find 11:
Step 1: [1, 3, 5, |7|, 9, 11, 13]  mid=7, 11>7, go right
Step 2: [9, |11|, 13]               mid=11, found!

Find 6 (not in array):
Step 1: [1, 3, 5, |7|, 9, 11, 13]  mid=7, 6<7, go left
Step 2: [1, |3|, 5]                 mid=3, 6>3, go right
Step 3: [5]                         mid=5, 6>5, go right
Step 4: []                          left>right, not found

Approach 1: Iterative Binary Search (Recommended)

Most efficient - no recursion overhead.

dartCopy
int binarySearch(List<int> arr, int target) {
  int left = 0;
  int right = arr.length - 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2;  // Avoid overflow

    if (arr[mid] == target) {
      return mid;  // Found!
    } else if (arr[mid] < target) {
      left = mid + 1;  // Search right half
    } else {
      right = mid - 1;  // Search left half
    }
  }

  return -1;  // Not found
}

void main() {
  List<int> numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

  print(binarySearch(numbers, 7));   // 3
  print(binarySearch(numbers, 13));  // 6
  print(binarySearch(numbers, 20));  // -1 (not found)
}

Time Complexity: O(log n) - divides search space in half each step Space Complexity: O(1) - only uses pointer variables

Why

left + (right - left) ~/ 2

• Prevents integer overflow in other languages
• In Dart, ints are arbitrary precision, but it's good practice
• Equivalent to
  textCopy

  (left + right) ~/ 2

  but safer

Approach 2: Recursive Binary Search

Elegant but uses call stack memory.

dartCopy
int binarySearchRecursive(List<int> arr, int target, [int? left, int? right]) {
  left ??= 0;
  right ??= arr.length - 1;

  // Base case: not found
  if (left > right) {
    return -1;
  }

  int mid = left + (right - left) ~/ 2;

  if (arr[mid] == target) {
    return mid;  // Found!
  } else if (arr[mid] < target) {
    // Search right half
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // Search left half
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

void main() {
  List<int> numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];

  print(binarySearchRecursive(numbers, 10));  // 4
  print(binarySearchRecursive(numbers, 16));  // 7
  print(binarySearchRecursive(numbers, 5));   // -1
}

Time Complexity: O(log n) Space Complexity: O(log n) - recursion call stack depth

When to use:

• Cleaner, more readable for some people
• Tree-based algorithms (natural recursion)
• Interview preference

When NOT to use:

• Very large datasets (stack overflow risk)
• Performance-critical code (iterative is faster)

Approach 3: Generic Binary Search

Search any comparable type.

dartCopy
int binarySearchGeneric<T extends Comparable>(List<T> arr, T target) {
  int left = 0;
  int right = arr.length - 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2;
    int comparison = arr[mid].compareTo(target);

    if (comparison == 0) {
      return mid;
    } else if (comparison < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

void main() {
  // Search integers
  List<int> numbers = [1, 3, 5, 7, 9];
  print(binarySearchGeneric(numbers, 5));  // 2

  // Search strings
  List<String> words = ['apple', 'banana', 'cherry', 'date'];
  print(binarySearchGeneric(words, 'cherry'));  // 2

  // Search doubles
  List<double> prices = [9.99, 19.99, 29.99, 39.99];
  print(binarySearchGeneric(prices, 19.99));  // 1
}

Approach 4: Custom Comparator

Search objects with custom comparison logic.

dartCopy
int binarySearchWith<T>(
  List<T> arr,
  T target,
  int Function(T a, T b) compare,
) {
  int left = 0;
  int right = arr.length - 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2;
    int comparison = compare(arr[mid], target);

    if (comparison == 0) {
      return mid;
    } else if (comparison < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

class Product {
  final String name;
  final double price;
  Product(this.name, this.price);
}

void main() {
  List<Product> products = [
    Product('Apple', 0.99),
    Product('Banana', 1.29),
    Product('Cherry', 2.99),
    Product('Date', 3.49),
  ];

  // Search by price
  int index = binarySearchWith(
    products,
    Product('', 2.99),
    (a, b) => a.price.compareTo(b.price),
  );

  print(index);  // 2
  print(products[index].name);  // Cherry
}

Complete Solution Class

Production-ready implementation with all features.

dartCopy
class BinarySearch {
  /// Iterative binary search - O(log n) time, O(1) space
  static int search(List<int> arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
      int mid = left + (right - left) ~/ 2;

      if (arr[mid] == target) return mid;
      if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  /// Recursive binary search - O(log n) time, O(log n) space
  static int searchRecursive(List<int> arr, int target, [int? left, int? right]) {
    left ??= 0;
    right ??= arr.length - 1;

    if (left > right) return -1;

    int mid = left + (right - left) ~/ 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] < target) {
      return searchRecursive(arr, target, mid + 1, right);
    } else {
      return searchRecursive(arr, target, left, mid - 1);
    }
  }

  /// Generic search for any comparable type
  static int searchGeneric<T extends Comparable>(List<T> arr, T target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      int comparison = arr[mid].compareTo(target);

      if (comparison == 0) return mid;
      if (comparison < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  /// Search with custom comparator
  static int searchWith<T>(
    List<T> arr,
    T target,
    int Function(T a, T b) compare,
  ) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      int comparison = compare(arr[mid], target);

      if (comparison == 0) return mid;
      if (comparison < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  /// Find insertion position (for inserting into sorted array)
  static int findInsertPosition(List<int> arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
      int mid = left + (right - left) ~/ 2;

      if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return left;
  }
}

Comparison Table

Comparison with 1 million elements:

• Linear search: ~1,000,000 comparisons
• Binary search: ~20 comparisons (log₂(1,000,000) ≈ 20)
• 50,000x faster!

Visualization Example

Finding 33 in sorted array:

dartCopy
void visualize() {
  List<int> arr = [10, 20, 30, 40, 50, 60, 70, 80, 90];
  int target = 33;

  int left = 0, right = arr.length - 1;
  int step = 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2;
    print('Step $step: left=$left, mid=$mid, right=$right, arr[mid]=${arr[mid]}');

    if (arr[mid] == target) {
      print('Found at index $mid!');
      return;
    } else if (arr[mid] < target) {
      print('  → 33 > ${arr[mid]}, search right');
      left = mid + 1;
    } else {
      print('  → 33 < ${arr[mid]}, search left');
      right = mid - 1;
    }
    step++;
  }

  print('Not found (would insert at index $left)');
}

// Output:
// Step 1: left=0, mid=4, right=8, arr[mid]=50
//   → 33 < 50, search left
// Step 2: left=0, mid=1, right=3, arr[mid]=20
//   → 33 > 20, search right
// Step 3: left=2, mid=2, right=3, arr[mid]=30
//   → 33 > 30, search right
// Step 4: left=3, mid=3, right=3, arr[mid]=40
//   → 33 < 40, search left
// Not found (would insert at index 3)

Edge Cases

dartCopy
void testEdgeCases() {
  // Empty array
  assert(BinarySearch.search([], 5) == -1);

  // Single element - found
  assert(BinarySearch.search([5], 5) == 0);

  // Single element - not found
  assert(BinarySearch.search([5], 3) == -1);

  // Two elements
  assert(BinarySearch.search([1, 3], 1) == 0);
  assert(BinarySearch.search([1, 3], 3) == 1);

  // Target at start
  assert(BinarySearch.search([1, 2, 3, 4, 5], 1) == 0);

  // Target at end
  assert(BinarySearch.search([1, 2, 3, 4, 5], 5) == 4);

  // Target in middle
  assert(BinarySearch.search([1, 2, 3, 4, 5], 3) == 2);

  // Target smaller than all
  assert(BinarySearch.search([10, 20, 30], 5) == -1);

  // Target larger than all
  assert(BinarySearch.search([10, 20, 30], 40) == -1);

  // Duplicates (returns any occurrence)
  List<int> dups = [1, 2, 3, 3, 3, 4, 5];
  int index = BinarySearch.search(dups, 3);
  assert(index >= 2 && index <= 4);
}

Best Practices

1. Always Check if Array is Sorted

dartCopy
// ✅ Verify before search
bool isSorted(List<int> arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) return false;
  }
  return true;
}

int safeBinarySearch(List<int> arr, int target) {
  if (!isSorted(arr)) {
    throw ArgumentError('Array must be sorted for binary search');
  }
  return BinarySearch.search(arr, target);
}

2. Use Iterative for Production

dartCopy
// ✅ Preferred - no stack overflow risk
int search(List<int> arr, int target) => BinarySearch.search(arr, target);

// ⚠️ Use carefully - can overflow on huge datasets
int searchRec(List<int> arr, int target) => BinarySearch.searchRecursive(arr, target);

3. Handle Not Found Gracefully

dartCopy
// ✅ Good - check return value
int index = BinarySearch.search(numbers, target);
if (index != -1) {
  print('Found at $index');
} else {
  print('Not found');
}

// ❌ Bad - assumes found
print(numbers[BinarySearch.search(numbers, target)]);  // Crashes if -1!

4. Know When to Use Linear Search

dartCopy
// ❌ Inefficient - sorting cost > linear search for small data
void findInSmallList(List<int> arr, int target) {
  arr.sort();  // O(n log n)
  BinarySearch.search(arr, target);  // O(log n)
}

// ✅ Better for small lists (< 20 elements)
void findInSmallList(List<int> arr, int target) {
  arr.indexOf(target);  // O(n) but faster for small n
}

Interview Tips

Common Interview Questions:

Q: "What's the prerequisite for binary search?"

• Array MUST be sorted
• Random access (array, not linked list)

Q: "Why is it O(log n)?"

• Each iteration cuts search space in half
• log₂(n) iterations to reduce n to 1
• Example: 1000 elements → 10 steps max

Q: "Iterative vs Recursive?"

• Iterative: O(1) space, faster, production-ready
• Recursive: O(log n) space, cleaner code, educational
• Both O(log n) time

Q: "What if there are duplicates?"

• Standard binary search returns any occurrence
• For first/last occurrence, use modified versions (see Q417)

Follow-up Questions:

• "Find insertion position" → Return
  textCopy

  left

  pointer when not found
• "Search in rotated sorted array" → Modified binary search
• "Find peak element" → Binary search variant
• "Square root using binary search" → Search space is 0 to n

Red Flags to Avoid:

• Forgetting to mention sorted prerequisite ❌
• Saying "O(n) time complexity" ❌
• Not handling empty array ❌
• Infinite loop (wrong loop condition) ❌

Pro Tips:

• Draw the array and show pointer movement
• Explain why you use
  textCopy

  mid = left + (right - left) ~/ 2

• Mention that Dart's
  textCopy

  indexOf()

  is O(n), not binary search
• Compare with real-world examples (phone book, dictionary)

Resources

• Binary Search - Wikipedia
• Dart List API
• Binary Search Visualization