Binary Search

Binary Search is one of the most powerful techniques in computer science. It reduces search time from O(n) to O(log n) by eliminating half the search space in each step.

Real-World Analogy: The Dictionary

Imagine searching for "inheritance" in a physical dictionary. You wouldn't flip page by page from the start. Instead:

1. •Open somewhere in the middle, land on "M"
2. •"Inheritance" comes before "M" → search left half
3. •Open the left half, land on "F"
4. •"Inheritance" comes after "F" → search right half
5. •Continue until you find "I" section

Each step eliminates half the pages. This is binary search!

Visual Comparison:

Why O(log n)?

• •Each step cuts the search space in HALF
• •n → n/2 → n/4 → n/8 → ... → 1
• •Takes log₂(n) steps to reduce n elements to 1
• •log₂(1,000,000) ≈ 20 steps for a million elements!

Binary search isn't just for sorted arrays. Recognize these patterns:

1. Sorted Array Lookups

• •Find exact value
• •Find insertion position
• •Find first/last occurrence

2. Rotated Sorted Arrays

• •Array was sorted, then rotated
• •One half is always sorted

3. Binary Search on Answer

• •"Find minimum X such that..."
• •"Find maximum speed/capacity"
• •Search the answer space, not an array!

4. Finding Boundaries

• •First element ≥ target (lower bound)
• •Last element ≤ target (upper bound)
• •First position where condition becomes true

5. Peak/Valley Finding

• •Find local maximum or minimum
• •Find turning point in bitonic array

Recognition Signals:

• •"Sorted array" or "monotonic"
• •"O(log n) required"
• •"Find minimum/maximum that satisfies..."
• •"Minimize the maximum" / "Maximize the minimum"

Key Requirement: There must be a monotonic condition - once it becomes true (or false), it stays that way. This lets us eliminate half the space.

Every binary search follows these four steps:

Step 1: Define the Search Space The search space contains all possible values. Define left and right pointers.

Step 2: Narrow the Search Space Compare middle element to target. Eliminate half each iteration.

Step 3: Choose Exit Condition

• •while (left <= right) → exits when left > right (exact match)
• •while (left < right) → exits when left == right (boundary finding)

Step 4: Return the Correct Value

• •For exact match: return mid when found, -1 when not found
• •For boundaries: return left (they converge to the answer)

Calculating Midpoint (IMPORTANT):

The classic binary search for finding an exact match.

Walkthrough: Finding 7 in [1, 3, 5, 7, 9, 11, 13]

Walkthrough: Finding 4 (not in array)

Key Points:

• •Use left <= right (includes when left == right for single element)
• •Use mid = left + (right - left) / 2 to avoid overflow
• •Both boundaries move: left = mid + 1 and right = mid - 1

Watch how binary search eliminates half the remaining elements with each comparison.

Understanding edge cases solidifies your grasp of binary search termination.

Case 1: Empty Array

Case 2: Single Element Array

Case 3: Target Not in Array

Key Insight: When left > right, the pointers have "crossed" - the search space is empty. This is why we use left <= right: we continue searching as long as there's at least one element (when left == right).

Target at Boundaries:

• •Target is first element → works (mid eventually reaches index 0)
• •Target is last element → works (mid eventually reaches last index)

When duplicates exist, find the first or last occurrence of a value.

Problem: In [1, 2, 2, 2, 3], find first and last index of 2.

Visualization - Find First (Lower Bound):

Key Insight:

• •For FIRST occurrence: when nums[mid] >= target, it MIGHT be the answer, so right = mid
• •For LAST occurrence: when nums[mid] <= target, it MIGHT be the answer, so left = mid

Loop Condition:

• •Use left < right (not <=)
• •Loop ends when left == right, which is the answer

A sorted array that has been rotated at some pivot point.

Example:

Key Insight: At any mid point, ONE half is ALWAYS sorted!

Visualization:

Decision Logic:

See how binary search identifies which half is sorted to decide the search direction.

Find the minimum element in a rotated sorted array.

Key Insight: The minimum is at the rotation point - where the sequence "breaks".

Visualization:

Example:

Instead of searching in an array, search in a RANGE of possible answers.

When to use:

• •"Find minimum X such that condition is satisfied"
• •"Find maximum speed/capacity/time"
• •"Minimize the maximum" or "Maximize the minimum"

Pattern:

Example: Koko Eating Bananas Koko has piles of bananas and h hours. Find minimum eating speed k.

Search Space:

• •Minimum possible: 1 (eat at least 1 banana/hour)
• •Maximum possible: max(piles) (finish largest pile in 1 hour)

Watch binary search find the minimum eating speed by testing the canFinish predicate.

Find a peak element (greater than its neighbors) in an array.

Key Insight: If nums[mid] < nums[mid + 1], a peak MUST exist on the right. Why? Either we keep going up, or we hit a peak.

Visualization:

Edge Cases:

• •nums[-1] = nums[n] = -∞ (array boundaries are valleys)
• •Multiple peaks may exist; find ANY one

This pattern also applies to:

• •Finding local minimum
• •Finding turning point
• •Bitonic array problems

Search in a matrix where rows and columns are sorted.

Type 1: Fully Sorted Matrix Each row starts greater than the previous row ends. Treat as 1D array!

Type 2: Row & Column Sorted (Search Matrix II) Start from top-right or bottom-left corner.

Even experienced developers make these mistakes. Learn them once, avoid them forever.

Pitfall 1: Integer Overflow in Midpoint

Pitfall 2: Infinite Loop

Pitfall 3: Wrong Loop Condition

Pitfall 4: Off-by-One in Boundary Updates

Pitfall 5: Empty Array Not Handled

Quick Reference Templates:

Decision Tree:

The Golden Rules:

1. •Always use mid = left + (right - left) / 2
2. •Think about which elements to INCLUDE vs EXCLUDE
3. •When in doubt, trace through a small example
4. •Test edge cases: empty array, single element, target not present