Lesson 11.3 · Binary Search
Rotated Sorted Arrays
After a rotation, at least one half around mid is still sorted. Check which, and whether the target lies inside it.
12 min
Think of it like this
A clock face starting at 4 instead of 12: [4, 5, 6, 7, 0, 1, 2]. Cut it anywhere, and one of the two pieces still reads in order. You can tell which piece by comparing its two ends.
1.Which half is sorted?
If nums[lo] <= nums[mid], the left half lo..mid is sorted; otherwise the right half mid..hi is. In the sorted half, a simple range check tells whether the target can be there; if not, it must be in the other half.
To find the rotation point (the minimum), compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the minimum is to the right of mid; otherwise it's at mid or to its left.
Remember
- One side of mid is always sorted.
- Use the sorted side's ends to decide where the target is.
- Minimum: compare mid with hi.
Common mistakes
- Comparing with nums[lo] for the minimum search (fails when the array isn't rotated).
- Using < instead of <= when lo == mid.