Q: How do you find the FIRST occurrence of an element in a sorted array? Why isn't a plain binary search enough?

Why it isn't enough: a plain binary search returns some matching index. Searching 3 in [1, 3, 3, 3, 5], mid lands in the middle and you get index 2, while the first occurrence is 1. The algorithm isn't wrong — it answers a different question. The simple but poor fix: after a hit, walk left linearly. That degrades to O(n) when every element is equal — the entire benefit of binary search is lost in the worst case. Mention this option in the interview, then reject it immediately. The right fix: don't stop on a match — keep searching to the left. In the half-open template that is exactly the lower bound: a[mid] < target → lo = mid + 1, otherwise hi = mid. When the loop ends, lo is the first index greater than or equal to target; the check a[lo] === target confirms presence. For the last occurrence: use the same template with a[mid] <= target — the result is the first index greater than target (the upper bound), and the last occurrence is lo - 1. A useful consequence: upperBound(x) - lowerBound(x) gives you the number of occurrences in O(log n). That is the standard solution to real problems like "how many events in a sorted log fall in this time range" — noting the practical link strengthens the answer. Complexity: O(log n) — including the worst case, unlike the linear-walk variant.

Q: "Find the minimum ship capacity to deliver the packages in D days." This is a binary search problem — how do you see that?

This is the binary search on the answer space pattern; build the answer in four steps. Step 1 — recognition: "The problem says 'find the minimum X such that a condition holds'. The array isn't sorted, but the answers can be: as capacity grows, the days needed can only fall. That's monotonicity, so binary search applies." Step 2 — verify monotonicity out loud — the strongest part of the answer: "Increasing capacity never requires more days, so feasible has the shape false...false, true...true. If it didn't, binary search wouldn't work." Step 3 — fix the bounds: lo = the heaviest package (below that, the package can never ship — omitting this detail is the classic mistake); hi = the sum of all weights (carrying everything in one day is always possible). The answer must lie in that range. Step 4 — write feasible(cap): load packages in order; when the current load would exceed cap, start a new day. At the end check days needed <= D. A simple O(n) pass. Then the ordinary lower-bound template: feasible(mid) → hi = mid, otherwise lo = mid + 1. Complexity: O(n log(sum)). Say it out loud and compare: testing every capacity one by one would be O(n × sum) — binary search makes that logarithmic. The family: the identical pattern reappears in "Koko eating bananas in H hours", "split books among k students", "integer square root" and "maximum servers within a budget". Noting that shows you solved a class of problems, not one problem.

Q: How do you search in a rotated sorted array ([4,5,6,7,0,1,2])?

The key observation — this one sentence unlocks the answer: "If you split the array in the middle, at least one half is always fully sorted." If you can say that, the rest is mechanics. The algorithm: compute mid; if a[mid] === target you're done. Otherwise decide which half is sorted: a[lo] <= a[mid] → the left half is sorted. If target lies in [a[lo], a[mid]) go left, else go right otherwise → the right half is sorted. If target lies in (a[mid], a[hi]] go right, else go left You still discard half each step, so it stays O(log n). Details worth care — mentioning these lifts the answer above average: The choice of <= versus < in the comparisons is critical; getting it right without checking boundary cases is hard With duplicate elements ([2,2,2,0,2]) the method breaks: when a[lo] == a[mid] == a[hi] you cannot tell which half is sorted. You then do lo++ and continue, and the worst case becomes O(n). Raising that yourself is a strong signal Alternative approach: first binary-search for the rotation point (the minimum), then decide which half to search and run an ordinary binary search. Two phases, but the logic is clearer and harder to get wrong Dry-run is mandatory: walk target = 0 and target = 4 through [4,5,6,7,0,1,2] by hand — boundary mistakes surface exactly there.

Q: When should you NOT use binary search?

This question checks whether you apply the algorithm in the right place — answer with four concrete cases. (1) Unsorted data for a single lookup: the sort's O(n log n) exceeds a linear scan's O(n). "I'd sort and binary search" is wrong here. The break-even: for k lookups you compare n log n + k log n against k × n — as k grows, sorting wins. (2) When a hash map is better: if you only need existence or an exact key lookup, a hash map gives O(1), beating binary search's O(log n). Binary search wins only when you need order: range queries, nearest value, insertion point, first/last occurrence. (3) When there is no monotonicity: if the feasible function over the answer space can go back from "yes" to "no", binary search returns a wrong result — silently. That is the most dangerous case, because the code runs and may even be right on the test data. (4) When the structure has no random access: reaching mid in a linked list is O(n), so binary search's advantage evaporates — the total becomes O(n log n), worse than a plain linear scan. Closing sentence: "Binary search is not a tool that makes an expensive operation cheap — it is a tool that exploits order that already exists. If there is no order and creating it is expensive, I pick a different structure."

Question 1

Write a binary search and explain why it is correct.

Accepted Answer

What is assessed here is less the code and more how you justify it. Run the process like this: (1) Confirm the precondition: "The array is sorted — can you confirm?" That single question is a step many candidates skip. (2) Declare the template: "I'll use a half-open range: lo = 0, hi = n. The invariant is that the answer always lies in [lo, hi)." (3) Write the code and justify each line: mid = lo + (hi - lo) / 2 to avoid overflow; a[mid] < target → lo = mid + 1, because mid and everything to its left are smaller; otherwise hi = mid, because mid could still be the answer. (4) State the termination argument: "Each iteration either raises lo or lowers hi, so the range strictly shrinks — an infinite loop is impossible." (5) Dry-run — never skip this: on [5] with target = 3 (result: lo = 0, a[0] != 3 → not found) and target = 7 (result: lo = 1 — past the end). Two examples take 30 seconds and catch every off-by-one. (6) Complexity: O(log n) time, O(1) memory when written iteratively. Bonus sentence: "This template is also the lower bound — add an a[lo] === target check and it's an exact search, drop it and it's the insertion point. So one template is all you need to memorise."

Question 2

How do you find the FIRST occurrence of an element in a sorted array? Why isn't a plain binary search enough?

Accepted Answer

Why it isn't enough: a plain binary search returns some matching index. Searching 3 in [1, 3, 3, 3, 5], mid lands in the middle and you get index 2, while the first occurrence is 1. The algorithm isn't wrong — it answers a different question. The simple but poor fix: after a hit, walk left linearly. That degrades to O(n) when every element is equal — the entire benefit of binary search is lost in the worst case. Mention this option in the interview, then reject it immediately. The right fix: don't stop on a match — keep searching to the left. In the half-open template that is exactly the lower bound: a[mid] < target → lo = mid + 1, otherwise hi = mid. When the loop ends, lo is the first index greater than or equal to target; the check a[lo] === target confirms presence. For the last occurrence: use the same template with a[mid] <= target — the result is the first index greater than target (the upper bound), and the last occurrence is lo - 1. A useful consequence: upperBound(x) - lowerBound(x) gives you the number of occurrences in O(log n). That is the standard solution to real problems like "how many events in a sorted log fall in this time range" — noting the practical link strengthens the answer. Complexity: O(log n) — including the worst case, unlike the linear-walk variant.

Question 3

"Find the minimum ship capacity to deliver the packages in D days." This is a binary search problem — how do you see that?

Accepted Answer

This is the binary search on the answer space pattern; build the answer in four steps. Step 1 — recognition: "The problem says 'find the minimum X such that a condition holds'. The array isn't sorted, but the answers can be: as capacity grows, the days needed can only fall. That's monotonicity, so binary search applies." Step 2 — verify monotonicity out loud — the strongest part of the answer: "Increasing capacity never requires more days, so feasible has the shape false...false, true...true. If it didn't, binary search wouldn't work." Step 3 — fix the bounds: lo = the heaviest package (below that, the package can never ship — omitting this detail is the classic mistake); hi = the sum of all weights (carrying everything in one day is always possible). The answer must lie in that range. Step 4 — write feasible(cap): load packages in order; when the current load would exceed cap, start a new day. At the end check days needed <= D. A simple O(n) pass. Then the ordinary lower-bound template: feasible(mid) → hi = mid, otherwise lo = mid + 1. Complexity: O(n log(sum)). Say it out loud and compare: testing every capacity one by one would be O(n × sum) — binary search makes that logarithmic. The family: the identical pattern reappears in "Koko eating bananas in H hours", "split books among k students", "integer square root" and "maximum servers within a budget". Noting that shows you solved a class of problems, not one problem.

Question 4

How do you search in a rotated sorted array ([4,5,6,7,0,1,2])?

Accepted Answer

The key observation — this one sentence unlocks the answer: "If you split the array in the middle, at least one half is always fully sorted." If you can say that, the rest is mechanics. The algorithm: compute mid; if a[mid] === target you're done. Otherwise decide which half is sorted: a[lo] <= a[mid] → the left half is sorted. If target lies in [a[lo], a[mid]) go left, else go right otherwise → the right half is sorted. If target lies in (a[mid], a[hi]] go right, else go left You still discard half each step, so it stays O(log n). Details worth care — mentioning these lifts the answer above average: The choice of <= versus < in the comparisons is critical; getting it right without checking boundary cases is hard With duplicate elements ([2,2,2,0,2]) the method breaks: when a[lo] == a[mid] == a[hi] you cannot tell which half is sorted. You then do lo++ and continue, and the worst case becomes O(n). Raising that yourself is a strong signal Alternative approach: first binary-search for the rotation point (the minimum), then decide which half to search and run an ordinary binary search. Two phases, but the logic is clearer and harder to get wrong Dry-run is mandatory: walk target = 0 and target = 4 through [4,5,6,7,0,1,2] by hand — boundary mistakes surface exactly there.

Question 5

When should you NOT use binary search?

Accepted Answer

This question checks whether you apply the algorithm in the right place — answer with four concrete cases. (1) Unsorted data for a single lookup: the sort's O(n log n) exceeds a linear scan's O(n). "I'd sort and binary search" is wrong here. The break-even: for k lookups you compare n log n + k log n against k × n — as k grows, sorting wins. (2) When a hash map is better: if you only need existence or an exact key lookup, a hash map gives O(1), beating binary search's O(log n). Binary search wins only when you need order: range queries, nearest value, insertion point, first/last occurrence. (3) When there is no monotonicity: if the feasible function over the answer space can go back from "yes" to "no", binary search returns a wrong result — silently. That is the most dangerous case, because the code runs and may even be right on the test data. (4) When the structure has no random access: reaching mid in a linked list is O(n), so binary search's advantage evaporates — the total becomes O(n log n), worse than a plain linear scan. Closing sentence: "Binary search is not a tool that makes an expensive operation cheap — it is a tool that exploits order that already exists. If there is no order and creating it is expensive, I pick a different structure."

Variant	The question	Change to the template
Exact search	Does the element exist, and at which index?	Find the lower bound, then check `a[lo] === target`
First occurrence (lower bound)	The first index equal to target?	Condition: `a[mid] < target` → `lo = mid + 1`
Last occurrence (upper bound − 1)	The last index equal to target?	Condition: `a[mid] <= target` → `lo = mid + 1`, then take `lo - 1`
Insertion point	Where do I insert to keep the order?	It is the lower bound itself
Counting	How many times does target occur? How many in a range?	`upperBound(x) - lowerBound(x)`
Rotated array	Search in a rotated sorted array	Each step, decide which half is sorted; if target lies in it, go there
Search on the answer space	The minimum/maximum value satisfying a condition?	Search over the range `[min, max]`, not the array; replace the comparison with `feasible(mid)`

Binary search and search patterns

📚 Sources and documentation