Binary Search

Learning goal: Recognize when a sorted array lets you eliminate half of the candidates at every step.

Core idea A sorted array gives us directional information. After comparing the target with the middle value, every element on one side can be ruled out. Instead of checking values one by one, binary search keeps only the half that could still contain the target.

Algorithm plan

• Start with the complete index range.
• Inspect the value at the midpoint.
• Return immediately if it equals the target.
• Keep the right half when the midpoint is too small; keep the left half when it is too large.
• Return -1 when no indices remain.

Micro-example For [-1, 0, 3, 5, 9, 12] and target 9, the first midpoint is index 2, containing 3. Because 3 < 9, indices 0 through 2 cannot contain the target.

Pitfalls

• Binary search requires sorted data.
• The returned position is an index, not the value itself.
• The search must eventually discard the midpoint or stop on it.

Recap

• Sorting creates a useful left/right decision.
• Each comparison removes about half the candidates.
• An empty final range means the target is absent.

Learning goal: Explain why one midpoint comparison is enough to discard half of a sorted range.

Core idea Suppose the active range is [lo, hi] and its midpoint is mid. If nums[mid] is smaller than the target, then every index at or left of mid contains a value that is also too small. If nums[mid] is larger, every index at or right of mid is too large. The sorted order turns one comparison into a complete elimination step.

Data structure model

The array stays unchanged; only two index bounds move:

Use the inclusive convention [lo, hi]. If the midpoint is too small, set lo = mid + 1; if it is too large, set hi = mid - 1.

Micro-example With lo = 0, hi = 5, and mid = 2, the value 3 is too small for target 9. The next valid interval is [3, 5], not [2, 5], because index 2 has already been checked.

Pitfalls

• Keeping mid after a mismatch can cause an infinite loop.
• Mixing inclusive bounds with exclusive updates makes the invariant unclear.
• A comparison is about values, while movement is about indices.

Recap

• Sorted order makes each half eliminable.
• [lo, hi] contains all remaining candidates.
• Use mid + 1 and mid - 1 after checking mid.

Learning goal: Implement binary search with a safe midpoint and updates that guarantee progress.

Core idea We use a closed interval [lo, hi] and continue while lo <= hi. The midpoint is computed as lo + (hi - lo) / 2, with integer division. This form avoids adding two potentially large indices before dividing, and every mismatch removes the inspected midpoint from the next range.

Algorithm plan

1. Initialize lo = 0 and hi = nums.length - 1.
2. While lo <= hi, compute mid = lo + (hi - lo) / 2.
3. Compare nums[mid] with target.
4. Return mid if they are equal.
5. Set lo = mid + 1 when nums[mid] < target.
6. Otherwise set hi = mid - 1.
7. Return -1 after the interval becomes empty.

while lo <= hi:
    mid = lo + (hi - lo) / 2
    if nums[mid] == target: return mid
    if nums[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1

Micro-example For lo = 3 and hi = 5, mid = 3 + (5 - 3) / 2 = 4. If index 4 contains 9, the algorithm returns 4 without another update.

Pitfalls

• (lo + hi) / 2 can overflow in fixed-width integer languages.
• lo < hi belongs to a different boundary style; do not pair it casually with closed-interval updates.
• Forgetting integer division can produce a non-integer index.

Recap

• Closed interval means loop while lo <= hi.
• Safe midpoint: lo + (hi - lo) / 2.
• Every failed check moves a bound beyond mid.

Learning goal: Trace every bound and midpoint change on one complete search.

Core idea We will search [-1, 0, 3, 5, 9, 12] for 9 using the closed interval [lo, hi]. The first midpoint is index 2; since its value is too small, the target must lie strictly to its right. The next midpoint lands exactly on the target.

Algorithm plan

• Start with lo = 0, hi = 5.
• Compute the midpoint using the safe formula.
• Compare the midpoint value with 9.
• Update only the bound that excludes the impossible half.
• Stop as soon as equality is observed.

Micro-example Iteration 1: mid = 2, nums[mid] = 3; because 3 < 9, update lo to 3. Iteration 2: mid = 4, nums[mid] = 9; return index 4.

Pitfalls

• Do not move hi when the midpoint is smaller than the target.
• Do not return the midpoint value when the problem asks for its index.
• Preserve the original array order while moving only bounds.

Recap

• [0, 5] becomes [3, 5] after comparing with 3.
• The next midpoint is 4.
• The answer is index 4.

Learning goal: Diagnose the two implementation mistakes that most often break binary search.

Core idea Binary search is short, but its correctness depends on matching three choices: the midpoint formula, the interval convention, and the loop condition. A mathematically reasonable-looking update can still skip an answer or repeat the same midpoint forever if those choices disagree.

Algorithm plan

• For a closed interval, initialize hi to n - 1.
• Loop while lo <= hi so a one-element range is checked.
• Use mid = lo + (hi - lo) / 2.
• After checking mid, update with mid + 1 or mid - 1.
• Test an empty array only if the surrounding problem allows it.

Micro-example With lo = 3, hi = 3, lo <= hi is true, so the only remaining element is inspected. After a mismatch, hi = mid - 1 creates hi = 2, making the range empty.

Pitfalls

• Returning -1 before checking the final singleton range.
• Using lo = mid or hi = mid with an inclusive interval.
• Assuming a missing target has a valid insertion index.

Recap

• Safe midpoint prevents overflow.
• Loop and updates must share one boundary convention.
• Singleton and absent-target cases expose off-by-one bugs.

Learning goal: Relate the halving behavior to the O(log n) time bound and O(1) extra space.

Core idea After each comparison, the active range is roughly half as large. After k iterations, about n / 2^k candidates remain; the range becomes constant-sized when 2^k is comparable to n, so k is O(log n). The algorithm stores only a few indices, regardless of the array length.

Algorithm plan

• Maintain the invariant that the target can only be inside [lo, hi].
• Spend constant work computing mid and making one comparison.
• Shrink the interval by at least one element, usually by about half.
• Stop on equality or when the interval becomes empty.

Micro-example A range of 16 candidates shrinks approximately as 16 → 8 → 4 → 2 → 1. The array is not copied, and no recursive call stack is needed.

Pitfalls

• Binary search is not O(log n) on an unsorted array.
• Recursive implementations may use O(log n) stack space; the iterative version uses O(1).
• A tiny constant-time loop body does not change the logarithmic number of iterations.

Recap

• Time: O(log n) because the range is repeatedly halved.
• Extra space: O(1) for the iterative approach.
• Correctness depends on sorted input and consistent boundaries.