Search in rotated sorted array
StopBinary search
- CH1 lo
- CH2 hi
- CH3 mid
9/9
One half around any middle is sorted, and its ends say whether the target can be there.
Step through it →Binary Search
Binary search keeps a range that must hold the answer and halves it with every look, so a million candidates take about 20 steps.
Binary search: find the target's index
StopBinary search
numstarget
- CH1 lo
- CH2 hi
The target could be anywhere from lo = 0 to hi = 9.
Typical cost O(log n) time, O(1) spaceFull lesson: Binary Search →
When to reach for it
- The input is sorted, or the answers are: too small, then big enough.
- One cheap check tells you which side of a candidate the answer is on.
- A scan would work, but n is large.
- You want the smallest or largest value that still works.
What stays true
The list is sorted, so everything left of a too-small middle is smaller still, and everything right of a too-big one is larger. Each move drops only numbers that can't be the target.
The target never leaves the range
StopBinary search
InvariantIf the target is in nums, it's between lo and hi.✓ Holds
- CH1 lo
- CH2 hi
The target could be anywhere from lo = 0 to hi = 9.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
The target is the last candidate standing. A loop that runs while lo < hi stops before checking it.
Binary search on the inputs that trip it up
StopBinary search
- CH1 lo
- CH2 hi
The target could be anywhere from lo = 0 to hi = 5.
Answer5Steps7
Variants
Find minimum in rotated sorted array
StopBinary search
- CH1 lo
- CH2 hi
8/8
Compare the middle with the right end to find which side the drop is on.
Step through it →Koko eating bananas
StopBinary search
- CH1 left
- CH2 right
14/14
Search the speeds, not the piles: too slow, then fast enough from the answer on.
Step through it →Longest increasing subsequence
StopBinary search
38/38
Each number binary-searches a sorted list of the smallest tail for each length.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Binary search: find the target's index
StopBinary search
- CH1 lo
- CH2 hi
The target could be anywhere from lo = 0 to hi = 9.
search.py
def search(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid if nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1