Binary Search Fundamentals
Binary search finds a target in a sorted collection in O(log n). The key insight: at each step, eliminate half the search space by comparing the midpoint to the target. Common mistake: infinite loops from incorrect loop invariants or mid computation. Template: use left right, the element is not present. Return left for “insertion point” problems.
Classic Binary Search
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] list[int]:
def find_left():
lo, hi, result = 0, len(nums)-1, -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: result = mid; hi = mid - 1
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return result
def find_right():
lo, hi, result = 0, len(nums)-1, -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: result = mid; lo = mid + 1
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return result
return [find_left(), find_right()]Search in Rotated Sorted Array (LC 33)
The array was sorted then rotated at some pivot. One half is always sorted. Identify which half is sorted, check if target is in that half, eliminate the other half.
def search_rotated(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Binary Search on Answer Space
Many problems are solved by binary searching on the answer, not an array. Pattern: the answer is in some range [lo, hi]. Define a feasibility function check(x): “can we achieve X?” The function is monotonic (if X works, X+1 might work too — or might not). Binary search finds the boundary.
# Koko Eating Bananas (LC 875): minimum eating speed k
def min_eating_speed(piles: list[int], h: int) -> int:
def can_finish(k: int) -> bool:
return sum((p + k - 1) // k for p in piles) <= h
# ceil division: hours needed for pile p at speed k
left, right = 1, max(piles)
while left int:
def can_make(day: int) -> bool:
bouquets = flowers = 0
for d in bloomDay:
if d = m
if m * k > len(bloomDay): return -1
left, right = min(bloomDay), max(bloomDay)
while left < right:
mid = (left + right) // 2
if can_make(mid): right = mid
else: left = mid + 1
return leftFind Peak Element and Mountain Array
# Find Peak Element (LC 162): peak where nums[i] > neighbors
def find_peak_element(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left nums[mid + 1]:
right = mid # peak is at mid or to the left
else:
left = mid + 1 # peak is to the right
return left
# Mountain Array: find peak, then binary search both sides
def find_in_mountain(arr, target):
# Step 1: find peak
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < arr[mid+1]: lo = mid + 1
else: hi = mid
peak = lo
# Step 2: binary search ascending half [0, peak]
result = binary_search(arr[:peak+1], target)
if result != -1: return result
# Step 3: binary search descending half [peak+1, n-1] (reverse)
return binary_search(arr[peak+1:][::-1], target)
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What are the two binary search templates and when do you use each?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Template 1 (left <= right, exact match): use when searching for a specific value. Loop exits when left > right (element not found). Returns -1 on miss or index on hit. Template 2 (left < right, find boundary): use when finding the leftmost/rightmost position satisfying a condition, or when binary searching on an answer space. Loop exits when left == right, which is the answer. On each step: if mid satisfies condition, right = mid (answer is at mid or to the left). Otherwise, left = mid + 1. The choice of right = mid vs. right = mid – 1, and left = mid + 1 vs. left = mid, determines which boundary you find. Common mistake: using right = mid when the condition check is inclusive can cause infinite loops if left == mid — always verify the loop makes progress.”}},{“@type”:”Question”,”name”:”How do you identify that a problem requires binary search on the answer space?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Binary search on answer space applies when: (1) The answer is a number in some range [lo, hi] (min/max problems). (2) You can define a feasibility function check(x) that returns True/False. (3) The function is monotonic: if x works, then x+1 also works (or vice versa). The classic signal phrases: "minimum X such that…" or "maximum X such that…" or "minimum/maximum capacity/speed/days…". Examples: Koko Bananas (minimum speed), Capacity To Ship Packages (minimum capacity), Magnetic Force Between Balls (maximum minimum distance). The search space is the answer range (often 1 to max_possible_value). For each mid, run the feasibility check in O(n) or O(n log n) — total time O(n log(answer_range)).”}},{“@type”:”Question”,”name”:”Why does searching in a rotated sorted array work with the "identify sorted half" approach?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A rotated sorted array has exactly one rotation point. At any midpoint, one of the two halves (left half [left, mid] or right half [mid, right]) is always sorted — because the rotation point can be in at most one half. By comparing nums[left] to nums[mid]: if nums[left] <= nums[mid], the left half is sorted (no rotation point in it). Otherwise, the right half is sorted. Once you identify the sorted half: check if the target falls within that sorted half's range (O(1) comparison). If yes, binary search there. If no, the target must be in the other half. This maintains the O(log n) guarantee by eliminating half the search space on each step, just like standard binary search.”}},{“@type”:”Question”,”name”:”How do you find the minimum in a rotated sorted array without knowing the pivot?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The minimum element is always in the unsorted half (the half that contains the rotation point). Binary search: compare nums[mid] to nums[right]. If nums[mid] > nums[right]: the minimum is in the right half (mid+1 to right). If nums[mid] <= nums[right]: the minimum is in the left half including mid (left to mid). Shrink right = mid. Loop terminates when left == right — that is the minimum. Why compare to nums[right] instead of nums[left]: comparing to nums[right] avoids ambiguity when the array is not rotated (nums[left] <= nums[mid] always, so you cannot tell which half contains the minimum without a nums[right] comparison). This also handles duplicates variant (LC 154): if nums[mid] == nums[right], right– (shrink conservatively) — O(n) worst case with duplicates.”}},{“@type”:”Question”,”name”:”What is the "peak finding" binary search and why does it terminate correctly?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A peak element is one where nums[i] > nums[i+1] (right neighbor is smaller). Binary search: compare nums[mid] to nums[mid+1]. If nums[mid] < nums[mid+1]: the right side is ascending, so there must be a peak to the right (at least nums[mid+1] is a candidate). Set left = mid + 1. If nums[mid] > nums[mid+1]: nums[mid] is a candidate peak, and the peak is at mid or to the left. Set right = mid. Loop invariant: a peak always exists in [left, right]. When left == right: that element is the peak. Termination: the interval strictly shrinks each iteration (left = mid+1 increases left, or right = mid strictly decreases right since mid < right when left < right). No infinite loop. The problem guarantees nums[-1] = nums[n] = -infinity, so edge elements only need to beat one neighbor.”}}]}
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Apple Interview Prep