Binary Search: Beyond Simple Lookup
Master binary search and its powerful variants — search on rotated arrays, find boundaries, minimize/maximize with binary search on answer, and search in 2D matrices.
Binary Search: The Template
Binary search eliminates half the search space each iteration, achieving O(log n). The key challenge isn't the concept — it's getting the boundary conditions right. Off-by-one errors are the #1 source of bugs. Use a consistent template and stick to it.
def binary_search(nums: list[int], target: int) -> int:
"""Standard binary search. Returns index or -1."""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # Avoids overflow in other languages
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Finding Boundaries: bisect_left & bisect_right
Often you need the leftmost or rightmost position of a target, or the insertion point. bisect_left finds the first position where target could be inserted. bisect_right finds the position after all existing copies.
def bisect_left(nums: list[int], target: int) -> int:
"""Find leftmost insertion point (first index >= target)."""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def bisect_right(nums: list[int], target: int) -> int:
"""Find rightmost insertion point (first index > target)."""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def count_occurrences(nums: list[int], target: int) -> int:
return bisect_right(nums, target) - bisect_left(nums, target)Notice the difference: lo <= hi with lo = mid + 1 / hi = mid - 1 for exact search, vs lo < hi with hi = mid for boundary search. Pick one template and never mix them.
Search in Rotated Sorted Array
A rotated sorted array has two sorted halves. At each step, determine which half is sorted and whether the target falls in that range. This is a favorite interview question — the trick is correctly identifying the sorted half.
def search_rotated(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Binary Search on Answer
One of the most powerful patterns: when asked to minimize the maximum or maximize the minimum of something, binary search on the answer value. Define a feasibility function, then binary search for the boundary between feasible and infeasible.
def min_max_split(nums: list[int], k: int) -> int:
"""Split array into k subarrays minimizing the maximum sum."""
def can_split(max_sum: int) -> bool:
splits, current = 1, 0
for num in nums:
if current + num > max_sum:
splits += 1
current = num
if splits > k:
return False
else:
current += num
return True
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if can_split(mid):
hi = mid
else:
lo = mid + 1
return lo'Binary search on answer' applies to: splitting arrays, allocating resources, minimizing time/cost, Koko eating bananas, ship capacity, and many optimization problems. If the answer is monotonic (feasible beyond a threshold), binary search works.