28 questions using this pattern
Efficiently search sorted data by repeatedly dividing the search space in half. This transforms O(n) linear search into O(log n) by eliminating half the remaining possibilities with each comparison.
Imagine playing a number guessing game where someone says "higher" or "lower" after each guess. The optimal strategy is always guessing the middle—you eliminate half the possibilities each time regardless of the answer.
Another analogy: looking up a word in a physical dictionary. You don't read page by page from the start. You open roughly to the middle, see if you're before or after your word, then repeat in the appropriate half.
Binary search works because the data has monotonic ordering—if you find something too small, everything before it is also too small. If something is too big, everything after is also too big.
The key insight extends beyond simple arrays:
At each step, you make one comparison and eliminate half the space. After k comparisons, you've narrowed n elements down to n/2^k. Solving n/2^k = 1 gives k = log₂(n).
def binary_search(nums: list[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1We have a sorted array [1, 3, 5, 7, 9, 11, 13] and need to find the index of target value 9.
Example: Find target = 7 in sorted array
Array: [1, 3, 5, 7, 9, 11, 13]
L M R
Step 1: mid = 7, target = 7 → Found!
Example: Find target = 9
[1, 3, 5, 7, 9, 11, 13]
L M R
Step 1: mid = 7 < 9 → Search right half
L M R
Step 2: mid = 11 > 9 → Search left half
L
M
R
Step 3: mid = 9 → Found at index 4!
Binary search on answer: Minimum capacity to ship packages in D days
Search space: [max(weights), sum(weights)]
mid = some capacity
Can ship in D days with capacity mid?
Yes → try smaller capacity (go left)
No → need more capacity (go right)
Use this skeleton as a starting point for problems using this pattern:
def binary_search(arr: list, target: int) -> int:
"""Classic binary search for exact match."""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
def lower_bound(arr: list, target: int) -> int:
"""Find first position where arr[i] >= target."""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left # First valid position
def binary_search_answer(low: int, high: int, is_valid) -> int:
"""Binary search on answer space."""
while low < high:
mid = low + (high - low) // 2
if is_valid(mid):
high = mid # Try smaller
else:
low = mid + 1 # Need bigger
return lowLook for these keywords and patterns in problem descriptions:
Using (left + right) / 2 can overflow if left and right are both
large positive integers (in languages with fixed-size integers).
Fix:
Use left + (right - left) // 2 instead. This is mathematically
equivalent but avoids overflow.
Using right = mid with left <= right condition, or left = mid
when mid could equal left, causes infinite loops.
Fix:
For left <= right, always use left = mid + 1 and right = mid - 1.
For left < right, use left = mid + 1 and right = mid.
Find exact target in sorted array. Returns index or -1.
Examples: Binary Search, Search Insert Position
Find first or last position satisfying a condition. Used for ranges and counting occurrences.
Examples: First Bad Version, Find First and Last Position
Sorted array rotated at some pivot. One half is always sorted—determine which half and search appropriately.
Examples: Search in Rotated Sorted Array, Find Minimum
Search the space of possible answers. Need a monotonic predicate function to determine feasibility.
Examples: Capacity To Ship Packages, Koko Eating Bananas, Split Array Largest Sum
Find local maximum in bitonic array. Compare mid with neighbors to determine which side has the peak.
Examples: Find Peak Element, Find in Mountain Array
Start here to build foundational understanding.
Master the pattern with these representative problems.
Returning left when you should return left - 1 (or vice versa)
gives the wrong boundary element.
Fix:
Think carefully about loop invariants. What does left represent when
the loop ends? Test with edge cases.
Missing that a problem can use binary search because the "array" is implicit (search space of possible answers).
Fix:
If you need to minimize/maximize something and can write a function
is_valid(x) that's monotonic, binary search applies.