Micro-questions over the modified binary search pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The problem
1. Why does plain binary search fail on [4,5,6,7,0,1,2]?
Answer
The array is not fully sorted — it is sorted and then rotated at an unknown pivot, so comparing against nums[mid] no longer tells you which side the target is on.
2. State the key insight.
Answer
Even when the whole array is not sorted, at least one of the two halves around any mid is guaranteed to be sorted.
3. Why is that true?
Answer
There is exactly one rotation point, so it falls in one half and the other half is untouched.
4. What is a rotated sorted array?
Answer
A sorted array rotated at an unknown pivot — [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated at index 4.
B. The rotated search
5. How do you decide which half is sorted?
Answer
Compare nums[left] with nums[mid]. If nums[left] <= nums[mid], the left half is normally sorted; otherwise the right half is.
6. Once you know, what do you check?
Answer
Whether the target falls inside that sorted half’s range. If so, search there; otherwise the target must be in the other, still-rotated half.
7. Write the two branches.
Answer
if nums[left] <= nums[mid]: # left sorted
if nums[left] <= target < nums[mid]: right = mid - 1
else: left = mid + 1
else: # right sorted
if nums[mid] < target <= nums[right]: left = mid + 1
else: right = mid - 18. Trace target 0 on [4,5,6,7,0,1,2].
Answer
mid=3 (7); left half [4,5,6,7] sorted; 0 not in [4,7) → go right, left=4. mid=5 (1); left half [0,1] sorted; 0 in [0,1) → go left, right=4. mid=4 (0) → found at index 4.
9. Why do the range checks use half-open intervals (< on one end)?
Answer
nums[mid] has already been tested and rejected, so it must be excluded from both candidate ranges or the search can fail to shrink.
C. Binary search on the answer
10. What is the distinct variant?
Answer
Binary searching over the space of possible answers, not over array indices.
11. When does it apply?
Answer
When a problem asks for the optimal value satisfying a condition, and “is candidate X good enough?” is cheap to check and monotonic.
12. Define a monotonic predicate.
Answer
A condition that, once true, stays true for all larger values — every value below a threshold fails, every value at or above it works, with no flip-flopping.
13. Give two canonical examples.
Answer
Koko’s minimum eating speed to finish in hours; the minimum ship capacity to deliver in days. Also the minimum board size covering all holes with boards.
14. What is the cost?
Answer
where is the size of the answer range — and is small even for enormous ranges.
D. Trade-offs
15. What does rotated search assume?
Answer
That the array is sorted and rotated — not arbitrary unsorted data — and that there is exactly one rotation point.
16. What does binary search on the answer require?
Answer
A monotonic predicate. Not all optimisation problems have this property, and the technique returns a plausible wrong number when it is absent.
17. What happens with duplicates in a rotated array?
Answer
nums[left] == nums[mid] becomes ambiguous — you cannot tell which half is sorted. The worst case degrades to , and the standard fix is to shrink left by one and retry.
18. Summarise the pattern in one sentence.
Answer
Binary search needs only a way to discard half the space — not sortedness — so find the half you can reason about, whether that half is in an array or in a range of candidate answers.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Modified Binary Search — the pattern
- Linear & Binary Search — Question Bank
- Binary Search on the Answer — Question Bank — the variant in depth
Software engineering
Infrastructure & security
Computer science
Hardware & engineering