DSA · Pattern
Binary Search
Cut the search space in half each step. Works on sorted arrays and on "answer space" when you can check if a guess is valid.
Simple summary: Like finding a word in a dictionary — check the middle,
see if your target is before or after, and repeat. That gives O(log n) speed on sorted data.
Example: Find
7 in [1, 3, 5, 7, 9, 11] — middle is 5 (too small),
search the right half; middle is 9 (too big), search left of that; find 7 in three steps.
1. Classic binary search
Example: Find 7 in sorted [1, 3, 5, 7, 9, 11].
left, right = 0, n-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return mid
if nums[mid] < target: left = mid + 1
else: right = mid - 1
return -1
Walkthrough (find 7 in [1, 3, 5, 7, 9, 11]):
mid=2 → nums[2]=5 < 7 → left=3
mid=4 → nums[4]=9 > 7 → right=3
mid=3 → nums[3]=7 → return 3
2. When array is sorted
- Find exact value
- Find first / last position of target
- Find insert position
3. Binary search on answer (important)
Sometimes the array is not sorted, but the answer lies in a range and you can test each guess.
Example: "Can we ship all packages in D days?" — binary search on D from 1 to max days.
low = 1, high = maxPossibleDays
while low < high:
mid = (low + high) // 2
if canShip(allPackages, days=mid):
high = mid // mid works, try fewer days
else:
low = mid + 1 // mid too small, need more days
return low
Walkthrough:
canShip(10 days)? yes → try 5
canShip(5 days)? no → try 7
canShip(7 days)? yes → try 6
... smallest D that works is the answer
4. Common mistakes
- Infinite loop: use
left = mid + 1orright = mid - 1correctly - Overflow: use
mid = left + (right - left) // 2 - Using BS on unsorted data without a valid check function
Quick revision
- Sorted array → classic BS, O(log n).
- Min/max answer in range → BS on answer +
can(x)check. - Loop while
left <= right(orleft < rightfor bounds).