Q: Find Minimum in Rotated Sorted Array, distinct values. Loop while lo < hi. Which comparison is right?

if nums[mid] > nums[hi]: lo = mid + 1 else: hi = mid If mid is above hi the minimum is to the right, else mid could be it so keep it. Comparing with lo fails on a non rotated array (it moves past index 0). The flipped comparison walks away from the min. lo = mid with lo < hi can loop forever and hi = mid - 1 can skip the min.

Q: Koko Eating Bananas (find the minimum speed k bananas per hour, one pile per hour at most, that finishes all piles in h hours), n piles up to 10^4, pile sizes up to 10^9. Binary search on speed. What is the total time?

O(n log M) where M is the max pile Each candidate speed costs an O(n) feasibility check, and there are O(log M) candidates. O(log M) forgets the check. O(n log n) is sorting. O(M n) is trying every speed.

Q: Koko eats up to k bananas per hour from one pile and waits out the rest of the hour. How many hours does pile p take? Which is right with integers?

(p + k - 1) // k Ceiling division counts a partial hour. p // k undercounts. p / k is a float. p // k + 1 overcounts when k divides p.

Q: Capacity To Ship Packages Within D Days (least ship capacity that sends weights in order within D days). What are the search bounds for capacity?

lo = max(weights), hi = sum(weights) Capacity must carry the heaviest package and never needs more than all in one day. hi = max(weights) is too small when D is small. min is not a valid lower bound. sum // D can be below the heaviest package and the upper bound is wrong.

Q: When is binary search on the answer valid?

When feasibility is monotone: if x works then every larger x works (or every smaller) You need a predicate that flips once. Sorted input is not required, for example shipping weights stay in order. Integer answers alone do not give monotonicity. Convexity is ternary search territory.

Question 1

Find the first index with nums[i] >= x.lo, hi = 0, len(nums)
while lo <= hi:
 mid = (lo + hi) // 2
 if nums[mid] >= x: hi = mid
 else: lo = mid + 1

Accepted Answer

It can loop forever, the condition should be lo < hi With hi = mid, the half open template needs lo < hi; with lo <= hi, once lo == hi == mid the loop never ends, and mid can also index len(nums). It is not correct. When it does finish lo is the right answer, so it is not off by one. hi = len - 1 breaks the case where no element is >= x.

Question 2

In Java with int indices up to 2^31 - 1, why write mid = lo + (hi - lo) / 2?

Accepted Answer

lo + hi can overflow and go negative lo + hi above 2^31 - 1 wraps negative, the bug Joshua Bloch described in the JDK. Both forms round toward zero for non negative values. Speed is the same. Even lengths are not the issue.

Question 3

Search in Rotated Sorted Array (find target in a sorted array rotated at an unknown pivot) with distinct values. After computing mid, what tells you which half is sorted?

Accepted Answer

nums[lo] <= nums[mid] means the left half is sorted With distinct values, if nums[lo] <= nums[mid] the left part has no rotation point, and you check whether target falls in it. Comparing mid to target says nothing about where the rotation is. nums[mid] > nums[hi] means the right half holds the rotation, so the left is sorted, the opposite of the claim. Comparing only to nums[0] needs a separate pivot search to be correct.

Question 4

nums = [1, 2, 2, 2, 3]. What does bisect.bisect_left(nums, 2) return?

Accepted Answer

1 bisect_left returns the leftmost insertion point, index 1. 4 is bisect_right. 3 is the last 2's index. 2 is the middle.

Question 5

Count occurrences of x in a sorted array of n values. Best time?

Accepted Answer

O(log n) with bisect_right minus bisect_left Two binary searches give the range bounds in O(log n). Scanning is O(n). Finding one then expanding is O(log n + k), which degrades to O(n) when x repeats. Precomputing is O(n) setup and not given.

Question 6

Find Minimum in Rotated Sorted Array, distinct values. Loop while lo < hi. Which comparison is right?

Accepted Answer

if nums[mid] > nums[hi]: lo = mid + 1 else: hi = mid If mid is above hi the minimum is to the right, else mid could be it so keep it. Comparing with lo fails on a non rotated array (it moves past index 0). The flipped comparison walks away from the min. lo = mid with lo < hi can loop forever and hi = mid - 1 can skip the min.

Question 7

Koko Eating Bananas (find the minimum speed k bananas per hour, one pile per hour at most, that finishes all piles in h hours), n piles up to 10^4, pile sizes up to 10^9. Binary search on speed. What is the total time?

Accepted Answer

O(n log M) where M is the max pile Each candidate speed costs an O(n) feasibility check, and there are O(log M) candidates. O(log M) forgets the check. O(n log n) is sorting. O(M n) is trying every speed.

Question 8

Koko eats up to k bananas per hour from one pile and waits out the rest of the hour. How many hours does pile p take? Which is right with integers?

Accepted Answer

(p + k - 1) // k Ceiling division counts a partial hour. p // k undercounts. p / k is a float. p // k + 1 overcounts when k divides p.

Question 9

Capacity To Ship Packages Within D Days (least ship capacity that sends weights in order within D days). What are the search bounds for capacity?

Accepted Answer

lo = max(weights), hi = sum(weights) Capacity must carry the heaviest package and never needs more than all in one day. hi = max(weights) is too small when D is small. min is not a valid lower bound. sum // D can be below the heaviest package and the upper bound is wrong.

Question 10

When is binary search on the answer valid?

Accepted Answer

When feasibility is monotone: if x works then every larger x works (or every smaller) You need a predicate that flips once. Sorted input is not required, for example shipping weights stay in order. Integer answers alone do not give monotonicity. Convexity is ternary search territory.

Question 11

Median of Two Sorted Arrays of sizes m and n. Which array do you binary search and what is the time?

Accepted Answer

The shorter one, O(log min(m, n)) Partitioning the shorter array keeps the other partition index in range and gives O(log min). Searching the longer can produce invalid partitions. Merging is O(m + n), not logarithmic. Alternating has no clean invariant.

Question 12

Split Array Largest Sum into k contiguous parts so the largest part sum is as small as possible: give the binary search on answer.

Accepted Answer

Search the max part sum between max(nums) and sum(nums). For a candidate cap, greedily count parts by starting a new part when the running sum would exceed it. If parts <= k the cap is feasible, move hi down, else lo up. O(n log(sum)). Requires non negative values.

Binary search coding interview questions

More coding topics

Practise these on your commute