Binary Search

The idea

Imagine finding the word “quantum” in a paper dictionary. You don’t start at page 1. You open it near the middle, see you’re at “M”, and immediately know the word is in the second half. Then you split that half, and so on.

Binary search does exactly this on a sorted array:

1. Look at the middle element.
2. If it is the target — done.
3. If the target is bigger, throw away the left half. If it is smaller, throw away the right half.
4. Repeat on the half that is left.

Each step halves the number of candidates. That’s why it is so fast.

Step by step

We keep two indexes, low and high, marking the part of the array that could still contain the target:

low = 0, high = n - 1
while low <= high:
    mid = (low + high) // 2
    if a[mid] == target:  return mid
    if a[mid] <  target:  low  = mid + 1   # go right
    else:                 high = mid - 1   # go left
return -1                                  # not found

In the 3D model, ruled-out elements sink and fade, so you can see the remaining range shrink: 15 → 7 → 3 → 1.

Why O(log n)?

After k steps there are about n / 2ᵏ candidates left. We stop when that reaches 1, so 2ᵏ = n, which means k = log₂ n.

Doubling the data adds just one more step.

Code

def binary_search(a, target):
    low, high = 0, len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

a = [3, 9, 14, 21, 28, 35, 42, 50, 57, 63, 71, 78, 84, 90, 97]
print(binary_search(a, 63))   # 9
print(binary_search(a, 40))   # -1

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& a, int target) {
    int low = 0, high = (int)a.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // avoids integer overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> a = {3, 9, 14, 21, 28, 35, 42, 50, 57, 63, 71, 78, 84, 90, 97};
    cout << binarySearch(a, 63) << "\n";   // 9
}

Notice mid = low + (high - low) / 2 in C++. With very large arrays, low + high can overflow a 32-bit int; this form cannot.

Libraries have it built in: Python’s bisect module and C++’s std::lower_bound / std::binary_search.

Binary search is a way of thinking

The same “halve the search space” idea solves many problems that don’t look like searching at all:

• Find the first or last position of a value (lower / upper bound).
• Find the square root of a number to a given precision.
• “Binary search on the answer”: the minimum speed to finish a task in time, the largest possible minimum distance, and so on.
• git bisect finds the commit that introduced a bug by halving the history.

Common mistakes

• Using it on an unsorted array — the answer will be wrong, silently.
• Writing while low < high instead of <= and missing the last element.
• Updating low = mid or high = mid instead of mid ± 1, which can loop forever.