Find the Boundary: The Smallest Value in a Rotated List
The radio playlist from the last lesson, [40, 50, 60, 10, 20, 30], has a question hidden in it: where does the wrap happen, and what is the smallest track number? You could scan every item. But there is a yes-or-no question whose answer flips exactly once along the list, and any such flip can be found by binary search.
The rule
When yes-or-no flips only once, shrink toward the first yes.
Many problems hide a list of answers shaped like no, no, no, yes, yes, yes: every position gives "no" up to some point and "yes" after it. The answer you want is the first yes. One template finds it, and it is the most reusable piece of code in this section:
def first_true(lo, hi, is_ok):
while lo < hi:
mid = (lo + hi) // 2
if is_ok(mid):
hi = mid # mid might be the first yes: keep it
else:
lo = mid + 1 # mid is a no: drop it and everything before it
return loIt differs from the classic search in two ways, both deliberate. hi = mid keeps mid in the window, because a yes might be the first one. And the loop runs while lo < hi, stopping when the window is a single position: the answer. Since mid is always less than hi, every step shrinks the window, so it cannot get stuck.
For the rotated list, the question is "is this value no bigger than the last value?" Everything before the wrap is larger than the last item; everything from the smallest value onwards is not. So the first yes is the smallest value:
def rotation_min(nums):
i = first_true(0, len(nums) - 1, lambda i: nums[i] <= nums[-1])
return nums[i]The shortcut
Before writing any binary search, write the yes-no row out in words, like no no no yes yes yes. If it flips once, you need first_true and only the question itself. The question is the whole design.
Write the row
Is each value at most 30? 40 no, 50 no, 60 no, 10 yes, 20 yes, 30 yes. It flips once.
The trap is mixing templates: hi = mid - 1 from the classic search throws away a mid that might be the answer, and while lo <= hi with hi = mid can loop forever.
Drills
Answer fast — trust the rule.
For [15, 18, 2, 5, 9, 12], what is the yes-no row for "is the value at most 12"?
Why does first_true set hi = mid instead of hi = mid - 1 when is_ok(mid) is true?
What does rotation_min([1, 2, 3]) return for a list that was never rotated?
With vals = [3, 8, 14, 25, 25, 31, 40], what does first_true(0, len(vals), lambda i: vals[i] >= 50) return?
Remember
- When yes-or-no flips only once, shrink toward the first yes.
- Shortcut: write the yes-no row in words first; the question is the whole design.
- Trap: mixing templates, such as
hi = mid - 1with a first-yes search.