📖 Binary Search

The Dictionary Lookup Analogy

How do you find a word in a dictionary?

You don't start at page 1 and read every page. Instead:

1. Open to the middle
2. Is your word before or after this page?
3. Flip to the middle of the remaining half
4. Repeat until found

Each step eliminates half the possibilities!

Binary search works exactly like this. For sorted data, it finds elements in O(log n) time instead of O(n).

Why Binary Search is So Fast

Linear Search (The Slow Way)

Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Check 2... no
Check 5... no
Check 8... no
Check 12... no
Check 16... no
Check 23... FOUND! (6 checks)

Binary Search (The Fast Way)

Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Middle is 16... 23 > 16, search right half
[                   23, 38, 56, 72, 91]

Middle is 56... 23 < 56, search left half
[                   23, 38]

Middle is 23... FOUND! (3 checks)

The Power of Halving

Binary search on a billion items: 30 comparisons! That's the magic of O(log n).

How Binary Search Works

The Algorithm

1. Set LEFT pointer to start, RIGHT pointer to end
2. Find MIDDLE = (LEFT + RIGHT) / 2
3. If MIDDLE element is target → FOUND!
4. If MIDDLE element < target → search RIGHT half (LEFT = MIDDLE + 1)
5. If MIDDLE element > target → search LEFT half (RIGHT = MIDDLE - 1)
6. Repeat until found or LEFT > RIGHT (not found)

Visual Walkthrough

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
        L                              R
Find: 23

Step 1: mid = (0+9)/2 = 4 → arr[4] = 16
        23 > 16, search right
        [                  23, 38, 56, 72, 91]
                           L               R

Step 2: mid = (5+9)/2 = 7 → arr[7] = 56
        23 < 56, search left
        [                  23, 38]
                           L   R

Step 3: mid = (5+6)/2 = 5 → arr[5] = 23
        23 == 23, FOUND at index 5!

The Critical Requirement

Binary search works when the data is sorted.

Unsorted: [23, 5, 38, 12, 2, 91]
Binary search can fail here — it assumes elements are in order

Sorted:   [2, 5, 12, 23, 38, 91]
Binary search works as intended

If data isn't sorted, either sort it first (O(n log n)) or use linear search (O(n)).

Common Binary Search Variations

1. Find Exact Match

The basic version - find the target or return "not found."

2. Find First Occurrence

When duplicates exist, find the leftmost match:

Array: [1, 2, 2, 2, 3, 4]
Find first 2 → index 1 (not 2 or 3)

After finding a match, keep searching LEFT for earlier matches

3. Find Last Occurrence

Find the rightmost match:

Array: [1, 2, 2, 2, 3, 4]
Find last 2 → index 3

After finding a match, keep searching RIGHT for later matches

4. Find Insert Position

Where WOULD the target go to maintain sorted order?

Array: [1, 3, 5, 7]
Insert position for 4 → index 2 (between 3 and 5)

Binary Search Beyond Arrays

Binary search isn't just for finding elements. It works on any "search space" that has:

1. A sorted or monotonic structure
2. A way to check "too low" vs "too high"

Example: Square Root

Find the integer square root of 50:

Search space: [1, 2, 3, ..., 50]
Target: largest n where n² ≤ 50

mid=25: 25²=625 > 50 → too high, search left
mid=12: 12²=144 > 50 → too high, search left
mid=6:  6²=36 ≤ 50  → could be answer, but try higher
mid=9:  9²=81 > 50  → too high
mid=7:  7²=49 ≤ 50  → ANSWER!

Example: Find Minimum Capacity

"What's the minimum truck capacity to ship all packages in D days?"

Search space: [max_package_weight, sum_of_all_weights]

Binary search to find the minimum capacity where shipment is possible.

Common Mistakes

Off-by-One Errors

The #1 bug in binary search implementations:

Common mistakes:
- Using < when you need <=
- Setting left = mid instead of mid + 1
- Setting right = mid instead of mid - 1
- Wrong boundary (end vs end-1)

Integer Overflow

Risky:  mid = (left + right) / 2
        (if left + right exceeds integer max)

Better: mid = left + (right - left) / 2

Forgetting the Requirement

A good first question is: Is the data sorted? If not, binary search won't behave correctly.

When to Use Binary Search

FAQ

Q: What if the element isn't found?

Return -1, None, or the insert position depending on the problem.

Q: Can I binary search on floating point?

Yes! Use epsilon for termination instead of left > right.

Q: How do I choose between < and <= in the loop?

Use <= for finding exact matches. Use < for finding boundaries/insert positions.

Q: Why is it called "binary"?

Each step divides the search space in two (binary = two).

Q: What about ternary search?

Ternary search divides into thirds. It's useful for finding peaks in unimodal functions but not better for sorted arrays.

Summary

Binary search halves the search space with each step, achieving O(log n) efficiency on sorted data.

Key Takeaways:

• Works on sorted/monotonic data
• O(log n) - very large lists in a small number of steps
• Template: set bounds, find mid, narrow half, repeat
• Variations: first/last occurrence, insert position
• Works beyond arrays: any monotonic search space
• Watch for off-by-one errors
• Use left + (right - left) / 2 to avoid overflow

Binary search is fundamental - mastering it opens doors to many interview problems!