🔍 Binary Search Pattern
The O(log n) superpower - eliminate half the search space each step.
TL;DR
Sorted array + find something = Binary Search
Not just for "find element" - also for "find minimum/maximum satisfying condition."
The Core Idea
[1, 3, 5, 7, 9, 11, 13, 15, 17] target = 7
↑
mid
7 < 9? Yes → search left half
[1, 3, 5, 7, 9, ...]
↑
mid
7 > 5? Yes → search right half
[..., 7, 9, ...]
↑
mid
Found!
Time: O(log n) - halving each step Space: O(1) iterative, O(log n) recursive
Template 1: Standard Binary Search
Find exact target.
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
# nums = [1, 3, 5, 7, 9], target = 7
# Step 1: mid=2, nums[2]=5 < 7, left=3
# Step 2: mid=3, nums[3]=7 == 7, return 3
Interactive Demo
Binary Search
L↓
R↓
1
3
5
7
9
11
13
15
0
1
2
3
4
5
6
7
Search for 7 in sorted array. Start with full range.
left=0, right=7
1 / 3
View Code
def binary_search(nums, target):
left, right = 0, 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 -1Template 2: Find Leftmost (First Occurrence)
Find first position where condition is true.
def find_leftmost(nums: list[int], target: int) -> int:
left, right = 0, len(nums) # Note: right = len, not len-1
while left < right: # Note: < not <=
mid = left + (right - left) // 2
if nums[mid] >= target: # Move right when >=
right = mid
else:
left = mid + 1
return left # First position >= target
# nums = [1, 2, 2, 2, 3], target = 2
# Returns index 1 (first 2)
Use for: First occurrence, lower bound, insertion point
Template 3: Find Rightmost (Last Occurrence)
Find last position where condition is true.
def find_rightmost(nums: list[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target: # Move left when <=
left = mid + 1
else:
right = mid
return left - 1 # Last position <= target
# nums = [1, 2, 2, 2, 3], target = 2
# Returns index 3 (last 2)
Problem: Search in Rotated Sorted Array
Array rotated at pivot, find target.
[4, 5, 6, 7, 0, 1, 2] target = 0
↑
pivot
Left sorted: [4, 5, 6, 7]
Right sorted: [0, 1, 2]
def search_rotated(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
# 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 -1
Key insight: At least one half is always sorted.
Problem: Find Minimum in Rotated Array
def find_min(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# Min is in right half
left = mid + 1
else:
# Min is in left half (including mid)
right = mid
return nums[left]
# [4, 5, 6, 7, 0, 1, 2] → 0
Binary Search on Answer Space
When to use: "Find minimum X such that condition is satisfied"
Problem: Koko Eating Bananas
Find minimum speed to eat all bananas in h hours.
import math
def min_eating_speed(piles: list[int], h: int) -> int:
def can_finish(speed: int) -> bool:
hours = sum(math.ceil(pile / speed) for pile in piles)
return hours <= h
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid # Try slower
else:
left = mid + 1 # Need faster
return left
# piles = [3, 6, 7, 11], h = 8
# Binary search on speed: [1, 11]
# Speed 4: 1+2+2+3 = 8 hours ✓
Problem: Ship Packages Within D Days
def ship_within_days(weights: list[int], days: int) -> int:
def can_ship(capacity: int) -> bool:
day_count = 1
current_load = 0
for weight in weights:
if current_load + weight > capacity:
day_count += 1
current_load = 0
current_load += weight
return day_count <= days
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
Template Comparison
| Template | Loop | Pointer Update | Use Case |
|---|---|---|---|
| Standard | left <= right | left = mid + 1, right = mid - 1 | Find exact |
| Leftmost | left < right | right = mid | First occurrence |
| Rightmost | left < right | left = mid + 1 | Last occurrence |
| Answer | left < right | Based on feasibility | Min/max satisfying |
Common Mistakes
❌ Off-by-One Errors
# Wrong: infinite loop when left = right - 1
while left < right:
mid = (left + right) // 2
left = mid # Should be mid + 1
# Correct
left = mid + 1
❌ Integer Overflow
# Wrong (can overflow in some languages)
mid = (left + right) // 2
# Correct
mid = left + (right - left) // 2
❌ Wrong Initial Bounds
# For leftmost: right should be len(nums), not len(nums) - 1
left, right = 0, len(nums)
# For standard: right should be len(nums) - 1
left, right = 0, len(nums) - 1
Practice Problems
| Problem | Type | Difficulty |
|---|---|---|
| Binary Search | Standard | Easy |
| First Bad Version | Leftmost | Easy |
| Search Insert Position | Leftmost | Easy |
| Search in Rotated Array | Modified | Medium |
| Find Minimum in Rotated | Modified | Medium |
| Find Peak Element | Modified | Medium |
| Koko Eating Bananas | Answer Space | Medium |
| Capacity To Ship Packages | Answer Space | Medium |
| Median of Two Sorted Arrays | Advanced | Hard |
Quick Reference
# Standard: Find exact
while left <= right:
if nums[mid] == target: return mid
elif nums[mid] < target: left = mid + 1
else: right = mid - 1
# Leftmost: First >= target
while left < right:
if nums[mid] >= target: right = mid
else: left = mid + 1
return left
# Answer space: Min feasible
while left < right:
if feasible(mid): right = mid
else: left = mid + 1
return left
Next: BFS/DFS → - Graph and tree traversal patterns.