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)See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Apple Interview Prep