Binary Search and Its Variations
Binary search is simple to state and easy to get wrong. This guide covers lower and upper bound, searching a rotated array, and searching on the answer, with tested code.
Binary search finds a value in a sorted array in O(log n) time by comparing with the middle element and discarding the half that cannot contain the target. Interviewers expect the variations: lower and upper bound for first and last occurrence, rotated arrays where one half is always sorted, and searching on the answer with a monotonic check.
Binary search finds a value in a sorted array in O(log n) time by halving the search range each step. The real skill is not the textbook version but its variations: first or last occurrence, rotated arrays, and searching over a range of possible answers.
- Binary search runs in O(log n) time, which is about 20 steps for a million items and 30 steps for a billion.
- Computing the binary search midpoint as lo + (hi - lo) // 2 avoids the 32-bit integer overflow that lo + hi can cause in Java or C++.
- Lower bound and upper bound differ by one comparison, < versus <=, and their difference gives the count of a value in a sorted array.
- In a rotated sorted array, splitting at the middle always leaves at least one sorted half, which keeps the search O(log n) when values are distinct.
- Binary search on a rotated array with duplicates can degrade to O(n) in the worst case, because equal ends hide which half is sorted.
- Binary search on the answer works only when the check function is monotonic, false below a threshold and true above it.
01What it does and why it is fast
Binary search needs data that is sorted, or more generally a yes/no question whose answer flips exactly once as you move through the range. You look at the middle. That one comparison tells you which half cannot contain the target, so you discard it and repeat on the other half.
The number of steps is the number of times you can halve n before reaching 1, which is log base 2 of n. For a million items that is 20. For a billion it is 30. This is why a sorted array plus binary search beats a linear scan so heavily once n is large.
02Writing it so it does not break
Most bugs come from deciding what the range means. A reliable habit is the half-open range [lo, hi): lo is a valid index, hi is one past the end. The loop runs while lo < hi.
Compute the middle as lo + (hi - lo) // 2. In Python the simpler (lo + hi) // 2 is fine because integers do not overflow, but in Java or C++ lo + hi can overflow a 32-bit int when the array is huge. The safe form costs nothing, so use it everywhere.
A second habit: decide up front what you return when the target is missing. Returning the position where it would be inserted is more useful than returning -1, and it is exactly what the next section builds.
03Lower bound and upper bound
def lower_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] <= x:
lo = mid + 1
else:
hi = mid
return lo
a = [1, 2, 4, 4, 4, 7, 9]
print(lower_bound(a, 4)) # 2
print(lower_bound(a, 5)) # 5
print(lower_bound(a, 10)) # 7
print(upper_bound(a, 4)) # 5
print(upper_bound(a, 4) - lower_bound(a, 4)) # 3The two functions differ by one character, < versus <=. With them you can find the first occurrence, the last occurrence (upper_bound - 1), the count of a value (the difference, 3 here), and the insertion point for a missing value. Python ships the same thing as bisect.bisect_left and bisect.bisect_right, so in real code you would call those.
04Searching a rotated sorted array
A sorted array is rotated at some point, for example [4, 5, 6, 7, 0, 1, 2]. You cannot run plain binary search because the whole array is not in order. But if you split at the middle, at least one half is always sorted.
def search_rot(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
m = (lo + hi) // 2
if a[m] == t:
return m
if a[lo] <= a[m]: # left half is sorted
if a[lo] <= t < a[m]:
hi = m - 1
else:
lo = m + 1
else: # right half is sorted
if a[m] < t <= a[hi]:
lo = m + 1
else:
hi = m - 1
return -1
print(search_rot([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rot([4, 5, 6, 7, 0, 1, 2], 3)) # -1This one uses a closed range [lo, hi], so the loop runs while lo <= hi. Mixing the two styles inside one function is a classic source of off-by-one errors, so pick one per function.
If the array can contain duplicates, a[lo] <= a[m] stops being enough. With [1, 0, 1, 1, 1] and target 0, a[lo] == a[m] makes the left half look sorted, so the code discards the half holding the 0 and returns -1. The usual fix is to shrink both ends when a[lo] == a[m] == a[hi], and the worst case then degrades to O(n).
05Binary search on the answer
Sometimes there is no array to search. Instead there is a number you are trying to minimise, and a function works(x) that returns true or false. If works is false below some threshold and true above it, you can binary search on x.
Example: packages with weights [1..10] must be shipped in 5 days, in order, and each day has a capacity limit. What is the smallest capacity that works?
def ship(weights, days):
lo, hi = max(weights), sum(weights)
def days_needed(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid
else:
lo = mid + 1
return lo
print(ship([1,2,3,4,5,6,7,8,9,10], 5)) # 15The lower limit is the heaviest single package, because a smaller capacity could never carry it. The upper limit is the total weight, which finishes in one day. The check runs in O(n) and is called about log(sum) times. The same template solves splitting an array into k parts with a minimal largest sum, eating bananas at a minimum speed, and placing routers to maximise the smallest gap.
06Mistakes that cost points
Infinite loops are the most common. If you write lo = mid with hi = mid style updates on a closed range, the range may never shrink when hi = lo + 1. Always check that each branch makes progress.
The second is using the wrong comparison when duplicates exist. Plain binary search returns some index holding the value, not necessarily the first. If the question asks for the first or last, use the bounds.
The third is forgetting that the array must be sorted in the order your comparison assumes. A descending array needs the comparisons flipped.
The fourth is searching on the answer when the check is not monotonic. If works(x) is true, then false, then true again, binary search gives garbage. Prove the monotonic property before you write any code.
Finally, test the edge cases: an empty array, one element, target smaller than everything, target larger than everything, and all elements equal.
07Common interview questions
Q: What is the time and space complexity?
A: O(log n) time. O(1) space for the loop version, O(log n) stack for the recursive version.
Q: How do you find the first occurrence of a value in a sorted array with duplicates?
A: Run lower bound. If the index is inside the array and a[i] == x, that is the first occurrence.
Q: Why not use (lo + hi) / 2?
A: In languages with fixed-size integers the sum can overflow. lo + (hi - lo) / 2 cannot.
Q: Can you binary search a linked list?
A: Not efficiently. Reaching the middle takes O(n), so the total is no better than a scan.
Q: How do you find the minimum in a rotated sorted array?
A: Compare a[mid] with a[hi]. If it is larger, the minimum is to the right of mid, otherwise it is at mid or to the left. This needs distinct values to stay O(log n).