Binary Search
Rotated still has a sorted half
Why it matters
Circular buffers, wrapped schedules, and rotated logs preserve most of their sorted structure even though the smallest value no longer comes first. Falling back to a scan discards that useful order. For [4, 5, 6, 7, 0, 1, 2], find target 0 in logarithmic time despite the rotation.
Example
Search in Rotated Sorted Array
nums was sorted then rotated; values are unique. Return the index of target or -1 in O(log n).
- Input
- nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- Output
- 4
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Search in Rotated Sorted Array
nums = [4, 5, 6, 7, 0, 1, 2], target = 0→4
The baseline, Scan every value, is O(n) · O(1). The better model below keeps this exact input and removes that bottleneck.
In [4, 5, 6, 7, 0, 1, 2], mid holds 7 and the left half 4 through 7 is ordered; target 0 lies outside it, so keep [0, 1, 2]. Finding the ordered half preserves logarithmic elimination instead of brute linear scanning.
With lo = 0 and hi = 6, mid = 3 holds 7. The values from nums[lo] = 4 through 7 are ordered, but target 0 is outside that range, so keep indexes 4 through 6.
Now mid = 5 holds 1, and the ordered half from index 4 to 5 spans 0 through 1. Target 0 lies there, so hi becomes 4; nums[4] is the target. At every step, identify an ordered half, test its endpoint range, and discard the half that cannot contain 0.
Visual anchor
Search in Rotated Sorted Array
nums
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.