What you will learn
- One loop invariant that removes off-by-one bugs.
- Searching a rotated sorted array.
- Binary search on the answer: when the search space is values, not indices.
Signals
- Sorted (or rotated sorted) input and O(log n) required.
- “Minimum value such that…” or “maximum value such that…” where checking a candidate is easy and feasibility is monotonic.
- Constraints like values up to 10⁹, which rule out trying every value.
The lower-bound template
Search the half-open range [lo, hi). If nums[mid] < target, the answer is right of mid; otherwise mid might be the answer, so keep it with hi = mid. The loop ends when lo == hi, which is the answer. Most binary-search variants reduce to “find the first index where a condition becomes true”.
Code
"""Binary search: on sorted arrays, rotated arrays and on the answer itself."""
import math
def lower_bound(nums, target):
"""First index with nums[i] >= target (len(nums) if none)."""
lo, hi = 0, len(nums) # search in [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
def min_eating_speed(piles, hours):
"""Smallest speed k so all piles finish within `hours` (binary search on the answer)."""
def feasible(k):
return sum(math.ceil(p / k) for p in piles) <= hours
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid works; maybe something smaller does too
else:
lo = mid + 1
return lo
if __name__ == "__main__":
print(lower_bound([1, 3, 3, 5, 8], 3), lower_bound([1, 3, 3, 5, 8], 4), lower_bound([1, 3], 9))
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0), search_rotated([4, 5, 6, 7, 0, 1, 2], 3))
print(min_eating_speed([3, 6, 7, 11], 8))
Output:
1 3 2
4 -1
4
lower_boundreturns the first index ≥ target: 1 for 3, 3 for 4, andlen(nums)= 2 when nothing qualifies. Python’sbisect.bisect_leftdoes the same.- Rotated array: at least one half around
midis sorted. Check whether the target lies in the sorted half’s range; if not, it’s in the other half. - On the answer: for eating speed
k,feasible(k)is monotonic: if speed k works, any faster speed works. Find the smallest feasible k between 1 andmax(piles). Cost: O(n log max).
Recognising “binary search on the answer”
Ask: “If I guessed the answer, could I check it quickly? And if a guess works, do all larger (or smaller) guesses work?” If yes to both, binary search the guess. Classic examples: ship packages within D days, split array largest sum, minimum days to make bouquets, aggressive cows.
Practise: binary search problems.
Key takeaways
- Use a half-open
[lo, hi)range and “first index where condition holds” to avoid off-by-one bugs. - In a rotated array, one half around
midis always sorted; use it to decide. - Binary search on the answer needs a fast check and monotonic feasibility.
(lo + hi) // 2is fine in Python; in Java/C++ uselo + (hi - lo) / 2to avoid overflow.
Exercises
- Write
upper_bound(first index > target) and use both to count occurrences of a value. - Find the minimum in a rotated sorted array.
- Solve “capacity to ship packages within D days” with binary search on the answer.
Quiz
- In
lower_bound, why is ithi = midand nothi = mid - 1? - What two properties make binary search on the answer valid?
- Why is
(lo + hi) / 2risky in Java?
Show answers
nums[mid] >= target, somiditself may be the answer and must stay in the range.- A fast feasibility check for a candidate, and monotonic feasibility (once a value works, all larger, or all smaller, values work).
lo + hican overflow a 32-bit int for large indices;lo + (hi - lo) / 2avoids it.