Binary Search — The Guessing Game

Real-world analogy

What is it?

Binary search is a divide-and-conquer algorithm that finds a target value within a sorted array. By comparing the target to the middle element and eliminating half the search space each time, it achieves O(log n) time complexity — meaning it can search through a billion elements in about 30 steps.

Real-world relevance

Binary search is used everywhere: database indexes find records in huge tables, version control 'git bisect' finds the commit that introduced a bug, spell checkers look up words in dictionaries, and even debugging uses binary search when you narrow down which half of the code contains the bug.

Key points

• The Number Guessing Game — I am thinking of a number between 1 and 100. You guess, and I say 'higher' or 'lower.' The smartest strategy? Always guess the middle! First guess: 50. If 'higher,' guess 75. If 'lower,' guess 25. You will find any number in at most 7 guesses (because 2^7 = 128 > 100).
• What is Binary Search? — Binary search is an algorithm that finds a target value in a SORTED array by repeatedly dividing the search range in half. At each step, it compares the middle element with the target and eliminates half of the remaining elements.
• Why Sorted Data is Required — Binary search only works on sorted data. Why? Because when we check the middle and our target is larger, we know ALL elements in the left half are also smaller — so we can safely ignore them. Without sorting, we cannot make this guarantee.
• The Algorithm Step by Step — Start with low = 0, high = n-1. Find mid = (low + high) / 2. If arr[mid] == target, found it! If arr[mid] target, search left half: high = mid - 1. Repeat until low > high (not found).
• How Fast is Binary Search? — Each step cuts the search space in half. For 1000 elements: 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. That is only about 10 steps! For a million elements, only about 20 steps. This is O(log n) — incredibly fast.
• Linear Search vs Binary Search — Linear search checks every element one by one — O(n). For 1 billion elements, that is 1 billion checks. Binary search on sorted data? Only about 30 checks! That is the power of halving — it turns impossibly large searches into instant lookups.
• Common Pitfall: Integer Overflow in Mid — Writing mid = (low + high) / 2 can overflow if low + high exceeds the int range. The safe way is mid = low + (high - low) / 2. This calculates the same value but avoids overflow. Always use this in CP!
• Binary Search Beyond Arrays — Binary search is not just for finding values in arrays. You can binary search on the ANSWER to a problem! If you can check whether an answer x is valid, and validity is monotonic (all values below some point are invalid, all above are valid), you can binary search for that point.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Binary search in a sorted array
    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    int low = 0, high = n - 1;
    int result = -1; // -1 means not found

    while (low <= high) {
        int mid = low + (high - low) / 2; // Safe from overflow
        if (arr[mid] == target) {
            result = mid;
            break;
        } else if (arr[mid] < target) {
            low = mid + 1; // Target is in right half
        } else {
            high = mid - 1; // Target is in left half
        }
    }

    if (result != -1) {
        cout << "Found at index " << result << "\n";
    } else {
        cout << "Not found\n";
    }

    return 0;
}

Line-by-line walkthrough

1. 1. int low = 0, high = n - 1; — low and high define our current search range. We start by searching the entire array from index 0 to index n-1.
2. 2. int mid = low + (high - low) / 2; — we calculate the middle index. Using low + (high - low) / 2 instead of (low + high) / 2 prevents potential integer overflow.
3. 3. if (arr[mid] == target) — if the middle element IS our target, we found it! Store the index and break out of the loop.
4. 4. else if (arr[mid] < target) { low = mid + 1; } — if the middle element is smaller than our target, the target must be in the RIGHT half. We move low past mid to search only the right half.
5. 5. else { high = mid - 1; } — if the middle element is larger than our target, the target must be in the LEFT half. We move high before mid to search only the left half.
6. 6. while (low <= high) — we keep searching as long as our range is valid (low does not exceed high). If low becomes greater than high, the target is not in the array.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 6, target = 7;
    int low = 0, high = n;
    int result = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            result = mid;
            break;
        } else if (arr[mid] < target) {
            low = mid;
        } else {
            high = mid;
        }
    }

    cout << "Found at index: " << result << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Binary Search in 100 Seconds (YouTube)
• Binary Search Tutorial (CP-Algorithms)
• Binary Search Problems (CSES)