Binary Search

Core Concepts

Search space — the range [lo, hi] within which the answer is guaranteed to lie; every iteration discards at least half of the remaining space.

Monotonic predicate — a boolean function f(x) such that once it becomes True (or False) as x increases, it stays that way; binary search requires this property to be correct.

Invariant — lo ≤ answer ≤ hi is maintained after every iteration; the algorithm terminates when the search space collapses to a single candidate.

Feasibility function — in "binary search on answer" problems, a function feasible(k) that checks whether answer k is achievable; must be monotone over the answer space.

Convergence — the search space halves each step; for integer domains this guarantees termination in O(log n) steps regardless of the array's content.

---

Structural Invariants

---

Types / Variants

---

Key Algorithms

Exact Match

Finds the index of target in a sorted array; returns −1 if absent. Invariant: if target is present, it lies in [lo, hi].

• Time: O(log n), Space: O(1)

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

Lower Bound (First True / bisect_left)

Finds the leftmost position where arr[i] >= target. Everything left of lo is False; everything from hi onward is True.

• Time: O(log n), Space: O(1)

lo, hi = 0, len(arr)          # hi is exclusive; answer may be len(arr)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] < target: lo = mid + 1
    else: hi = mid
# return lo

Upper Bound (Last True / bisect_right)

Finds the leftmost position where arr[i] > target; subtract 1 for the last index ≤ target.

• Time: O(log n), Space: O(1)

lo, hi = 0, len(arr)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] <= target: lo = mid + 1
    else: hi = mid
# lo = first index > target; lo - 1 = last index <= target

Binary Search on Answer

Answer is an integer in [min_possible, max_possible] and feasible(k) is monotone. Frame as: find the minimum k where feasible(k) is True.

• Time: O(log(range) × cost(feasible)), Space: O(1)

lo, hi = min_possible, max_possible
while lo < hi:
    mid = lo + (hi - lo) // 2
    if feasible(mid): hi = mid
    else: lo = mid + 1
# return lo

Search in Rotated Sorted Array

One half of the array is always fully sorted even after an unknown rotation. Compare arr[lo] with arr[mid] to identify the sorted half, then check if target falls within it; eliminate the other half.

• Time: O(log n), Space: O(1)

Key insight: if arr[lo] <= arr[mid], the left half [lo, mid] is sorted; otherwise the right half [mid, hi] is sorted. Branch on whether target is inside the sorted half.

Peak Finding (Mountain Array / Bitonic)

If arr[mid] < arr[mid + 1], the peak lies to the right of mid; otherwise it lies at mid or to the left. The peak is always retained in [lo, hi] because the chosen half contains a higher element.

• Time: O(log n), Space: O(1)

---

Advanced Techniques

Floating-Point Binary Search

Solves problems where the answer is a real value (nth root, minimum real-valued speed, continuous allocation).

• What it solves: "Find minimum real x such that condition holds" with precision to 10⁻⁶ or 10⁻⁹.
• Core mechanism: run a fixed 100 iterations instead of lo < hi; each iteration: mid = (lo + hi) / 2.
• When to prefer over integer BS: answer is explicitly real-valued or fractional. Never apply to integer problems — floating-point mid can skip the correct integer.
• Time: O(100 × cost(feasible)) ≈ O(log(1/ε) × cost)

Parallel Binary Search

K independent binary searches over the same sorted structure, sharing a single data pass per round instead of K separate passes.

• What it solves: K offline queries each requiring a binary search over the same dataset (e.g., "for each query, find the kth event before time t").
• Core mechanism: maintain a [lo, hi] range per query; each round evaluate mid for every query, process all queries at their mid in one data sweep, then update each range. Repeat O(log N) rounds.
• When to prefer over independent searches: K is large and each query's data pass costs O(N) individually; overkill if each query is O(log N) independently.
• Time: O((K + N) log N)

Binary Search on BIT / Segment Tree Descent

Find the leftmost prefix sum ≥ k in O(log N) by descending the segment tree directly, eliminating the outer binary search loop.

• What it solves: k-th smallest element, order-statistics queries over dynamic sorted arrays.
• Core mechanism: at each node compare the left child's aggregate against k; if left ≥ k, descend left; else subtract left's value from k and descend right.
• When to prefer over simpler alternatives: array is dynamic (insertions/deletions); if static, precompute prefix sums and use bisect directly (O(log N) with no constant overhead).
• Time: O(log N) with segment tree descent vs. O(log² N) with BIT + outer binary search

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Wrong loop variant: using lo <= hi for a lower-bound search causes an infinite loop when lo == hi and arr[lo] >= target — hi = mid never shrinks the space. Match the template exactly to the variant (exact match uses lo <= hi; bounds use lo < hi).
• Stale mid stalling the loop: when lo == hi − 1, mid == lo; setting hi = mid leaves hi unchanged and loops forever. The lower-bound template avoids this because hi = mid with mid < hi always shrinks; the exact-match template avoids it via hi = mid − 1.
• Off-by-one in answer range: setting hi = max_val − 1 silently excludes the correct answer when it equals max_val. For "search on answer", set hi to the maximum possible value (e.g., sum(arr) for partition problems, not max(arr)).
• Returning lo vs. lo − 1: upper-bound and "last True" queries return lo = first index past the target; the actual answer is lo − 1, which may be −1 if all elements exceed the target.
• Non-monotone predicate: applying binary search to a predicate that flips True/False more than once gives a plausible-looking wrong answer. Verify monotonicity with a few examples before coding.
• Empty array: lo = 0, hi = −1 means the loop body never executes; returning 0 may be misinterpreted as a valid index. Check for empty input before calling binary search.
• Floating-point convergence: while lo < hi − 1e-9 can loop indefinitely when hi − lo oscillates near epsilon. Use a fixed iteration count (~100) for all real-valued searches.
• Overflow in mid computation: (lo + hi) // 2 overflows in C++/Java when both are near INT_MAX. Write lo + (hi − lo) // 2 when translating to fixed-width integer languages; Python integers are unbounded.
• All-equal values in rotated search: arr[lo] == arr[mid] makes it impossible to determine which half is sorted; worst case degrades to O(n) (LC 81 variant).

---

Implementation Notes

• Python's bisect module provides bisect_left (lower bound) and bisect_right (upper bound) directly; prefer these for index-based searches on plain lists.
• bisect_left(arr, x) returns the leftmost insertion point; arr[idx] == x only if x is actually present — always verify before accessing.
• For custom objects or keys, pass key= (Python 3.10+) or wrap values; alternatively use sortedcontainers.SortedList for O(log n) dynamic inserts with binary search.
• Set lo and hi to the tightest known bounds for "search on answer" — a loose [0, 10⁹] still converges in 30 iterations, but tighter bounds can halve that.
• When the answer space includes 0, initialize lo = 0, not lo = 1; missing 0 is a common source of wrong answers on edge inputs.
• bisect requires the list to already be sorted; calling it on an unsorted list gives silently wrong results with no error.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Basic Search

• Binary Search (LC 704) — exact match template
• Search Insert Position (LC 35) — lower bound
• Find First and Last Position of Element in Sorted Array (LC 34) — lower bound + upper bound together

Rotated Arrays

• Find Minimum in Rotated Sorted Array (LC 153)
• Search in Rotated Sorted Array (LC 33)
• Search in Rotated Sorted Array II — with duplicates (LC 81)

Peak Finding

• Find Peak Element (LC 162)
• Peak Index in a Mountain Array (LC 852)

Binary Search on Answer — Introductory

• Koko Eating Bananas (LC 875) — minimize maximum; classic entry point
• Capacity to Ship Packages Within D Days (LC 1011)

Binary Search on Answer — Intermediate

• Split Array Largest Sum (LC 410) — minimize maximum subarray sum
• Magnetic Force Between Two Balls (LC 1552) — maximize minimum gap
• Minimum Number of Days to Make m Bouquets (LC 1482)

Binary Search on Answer — Hard

• Median of Two Sorted Arrays (LC 4) — binary search on partition index; hardest in the tag
• Find K-th Smallest Pair Distance (LC 719)
• Minimize Maximum Distance to Gas Stations (LC 774) — floating-point BS

2D / Structural

• Search a 2D Matrix (LC 74)
• Kth Smallest Element in a Sorted Matrix (LC 378)

Additional LeetCode Coverage

• Find Minimum in Rotated Sorted Array II (LC 154)
• First Bad Version (LC 278)
• Intersection of Two Arrays (LC 349)
• Intersection of Two Arrays II (LC 350)
• Valid Perfect Square (LC 367)
• Find Right Interval (LC 436)
• Arranging Coins (LC 441)
• Single Element in a Sorted Array (LC 540)
• Valid Triangle Number (LC 611)
• Find Smallest Letter Greater Than Target (LC 744)
• Longest Arithmetic Subsequence (LC 1027)
• Find the Smallest Divisor Given a Threshold (LC 1283)
• Check If N and Its Double Exist (LC 1346)
• Number of Subsequences That Satisfy the Given Sum Condition (LC 1498)
• Kth Missing Positive Number (LC 1539)
• Successful Pairs of Spells and Potions (LC 2300)
• Longest Subsequence With Limited Sum (LC 2389)
• Sqrt(x) (LC 69)
• Minimize Max Distance to Gas Station (LC 774)

Clarification Questions to Ask

• Is the array guaranteed to be sorted, or must I sort it first?
• Can there be duplicate elements? (Affects rotated search and exact-match termination.)
• Should I return the index or the value?
• For "binary search on answer": what are the minimum and maximum possible answer values? (Needed to set lo and hi.)
• Is the answer an integer or a real value? (Determines template: fixed iterations vs. lo < hi.)
• For K-th element problems: is K 1-indexed or 0-indexed?

Common Interview Mistakes

• Using lo <= hi for a lower-bound search, then getting stuck in an infinite loop when lo == hi.
• Not verifying that the feasibility predicate is actually monotone before applying binary search.
• Setting hi = len(arr) − 1 instead of hi = len(arr) for lower/upper bound, causing the "insert at end" case to be missed.
• Returning lo instead of lo − 1 for upper-bound and "last True" queries.
• Setting hi = max(arr) instead of sum(arr) for partition/allocation problems where the answer can be the total sum.
• Hardcoding a feasibility threshold based on problem examples rather than deriving it from constraints, causing failure on edge inputs.

Typical Follow-Up Escalations

• "What if the array has duplicates?" → Rotated search degrades to O(n) worst case when arr[lo] == arr[mid] (LC 81); lower/upper bound is unaffected since monotonicity holds.
• "What if the array is infinite or its length is unknown?" → Exponential search: start with hi = 1, double until arr[hi] >= target, then binary search in [hi//2, hi].
• "Can you solve median of two sorted arrays in O(log(m+n))?" → Binary search on the partition index of the smaller array (LC 4).
• "What if queries arrive online and the array is updated between queries?" → Binary search on a BIT or segment tree for dynamic order statistics in O(log N) per operation.
• "Can you find the k-th smallest in a sorted matrix faster than O(n log n)?" → Binary search on value space + count function in O(n log(max−min)).