Binary Search

The guessing game

Think of it like this: “I'm thinking of a number from 1 to 100.” Guess 50 – “higher”. 75 – “lower”. 62... Each guess throws away half of what's left, so 7 guesses are always enough.

Binary search does this on a sorted vector: look at the middle, keep only the half where the target could be.

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

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

int main() {
    vector<int> v;
    for (int i = 0; i < 1000000; i++) v.push_back(i * 3);    // a million sorted numbers
    cout << binarySearch(v, 2999997) << endl;
    cout << binarySearch(v, 1234) << endl;
    return 0;
}

Output

(20 steps) 999999
(20 steps) -1

A million items, about 20 steps. That's O(log n).

Tip: low + (high - low) / 2 gives the same middle as (low + high) / 2 but can't overflow when the indexes are huge.

Common mistake: Binary search only works on sorted data. On unsorted data it quietly gives wrong answers.