Binary Search

Imagine you have a row of boxes. Each box has a number inside it. You don’t know the numbers, but you’re told the boxes are sorted in increasing order.

Now, you want to find whether a specific number x exists inside one of these boxes.

1. The Naive Way

Your first thought: “Let me open each box from left to right and check.”

That works, but in the worst case you’ll open all n boxes → O(n).

2. The Smarter Way

What if you could ignore half of the boxes at once?

How? By always checking the middle box:

• If a[mid] == x → found it.
• If a[mid] > x → you can safely ignore the right half (since everything there is larger).
• If a[mid] < x → ignore the left half.

Then, repeat the process on the remaining half.

This halves the range every step:

100 → 50 → 25 → 12 → 6 → 3 → 1

So in the worst case, you only open about log2(n) boxes.

That’s why binary search runs in O(log n).

3. Why Choose the Middle?

If you pick a random element (not the middle), you can’t guarantee you’ll eliminate a large part of the search space. The middle is optimal because it ensures we cut the range almost evenly each time.

4. Understanding Logarithm

log_x(y) = “How many times do I divide y by x until it becomes 1?”

For binary search, base = 2. So, log2(100) ≈ 7 → at most 7 steps to search among 100 elements.

5. C++ Implementation

// Standard Binary Search
int solve(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (a[md] == x) return md;     // found
        else if (a[md] < x) l = md + 1;
        else r = md - 1;
    }
    return -1; // not found
}

6. Binary Search on Answer (Important!)

Binary search isn’t only for searching in arrays. We often apply it when:

• We have many candidate answers.
• They follow a monotonic property (all bad → all good, or all good → all bad).

Examples:

1 1 1 1 1 0 0 0 → find the last "1"
0 0 0 0 0 1 1 1 → find the first "1"

We don’t search for a specific number, we search for the best candidate.

7. Upper Bound & Lower Bound

• lower_bound(a.begin(), a.end(), x) → first index with a[i] >= x.
• upper_bound(a.begin(), a.end(), x) → first index with a[i] > x.

Implementation of upper_bound:

int upper_bound(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    int res = -1;
    while (l <= r) {
        int md = (l + r) / 2;
        if (a[md] > x) {
            res = md;      // candidate answer
            r = md - 1;    // try smaller index
        } else {
            l = md + 1;
        }
    }
    return res;
}

8. When to Use Binary Search?

Whenever:

• You want the smallest or largest element satisfying a condition.
• You have a monotonic function (true/false transition).

9. Practice Problems

• Packing Rectangles
• Closest to the Left

Key Takeaways

• Binary search = cut search space in half each step.
• Runs in O(log n).
• Works on sorted arrays or monotonic answers.
• Super useful for answer searching, not only for array elements.

If the array is sorted, use binary search → O(log n). If the array is not sorted, don’t sort it just to apply binary search → instead use linear search → O(n), which is more efficient.