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.


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 - 1

8. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes