Binary Search

Binary Search is an efficient divide-and-conquer algorithm designed to locate a target value within a sorted array or list. By repeatedly halving the search space, it avoids checking every element individually, making it exponentially faster than linear search for large datasets.

Key Characteristics

Sorted Data Requirement

The input collection must be sorted beforehand. The algorithm relies on ordering to eliminate incorrect data sections.

Constant-Time Indexing

It requires random access data structures. It works perfectly with arrays but is highly inefficient with linked lists.

Three-Pointer Mechanic

It tracks data intervals using three primary markers: a low boundary pointer, a high boundary pointer, and a calculated midpoint pointer.

Search Space Halving:

Each comparison eliminates exactly half of the remaining items. If the target is smaller than the midpoint, the right half is discarded, and vice versa.

Time and Space Complexity

Best-Case Time Complexity: \(O(1)\)

Occurs when the target element matches the very first middle element checked.

Average-Case Time Complexity: \(O(log n)\)

Occurs because the algorithm halves the search space with every comparison step.

Worst-Case Time Complexity: \(O(log n)\)

Occurs when the target element is at the extreme ends of the array, or not present at all. The maximum number of comparisons needed is \(log2(n)\).

Space Complexity

Iterative Approach: \(O(1)\)

It uses a standard loop with a few pointers (low, high, and mid), requiring constant extra space.

Recursive Approach: \(O(log n)\)

Each split creates a new function call that gets added to the system call stack.

How It Works

1. Set two pointers to define your initial search boundaries.

2. Find the middle index of the current boundaries.

3. Compare the value at array[midpoint] with the target value.

4. Repeat steps and 3 as long as low <= high. If low becomes greater than high, the search boundaries have closed completely without finding the target. The algorithm terminates and returns -1 (indicating the item is not present).

Visualization

Source: GeeksforGeeks

Implementation

C++Python

template <int size>
int binarySearch(int (&array)[size], int target) {
  if (size == 0) return -1;
  int low { 0 }, high { size - 1 };
  while (low <= high) {
    int midpoint { low + (high - low) / 2 };
    if (array[midpoint] == target) return midpoint;
    if (array[midpoint] < target) {
      low = midpoint + 1;
    } else {
      high = midpoint - 1;
    }
  }
  return -1;
}

int main() {
  int array[] { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
  binarySearch(array, 23); // 5
}