Search a list that wraps
Find a value in a rotated sorted list by working out which half of each split is properly sorted. About 16 minutes.
One half is always sorted
Cut a rotated list at the middle. The wrap point, where the values drop, lies in at most one of the two halves. So at least one half is a plain sorted stretch, and you can tell which: if the first value is at most the middle value, the left half is sorted. Otherwise the right half is.
That gives you something to work with. A sorted half has a known smallest and largest value, its ends.
left_sorted = nums[low] <= nums[mid]
The middle is 9. The first value, 6, is at most 9, so the left half (6, 7, 8, 9) is sorted. Is 8 between 6 and 9? Yes, so look left.
Is the target in the sorted half
Once you know a half is sorted, check whether the target falls between its ends. If it does, keep that half and drop the other. If it doesn't, the target can only be in the other half, so go there.
Do this for whichever half is sorted. Be careful with the ends: the middle value was already checked, so the range test excludes it, and you move past it on either side.
in_left = nums[low] <= target < nums[mid]
In a rotated list, the first value is 6 and the middle is 2. Which half is sorted?
- AThe right half, because the first value is more than the middle so the wrap is on the left
- BThe left half
- CBoth halves
Show the answer
The right half, because the first value is more than the middle so the wrap is on the left. 6 is bigger than 2, so values drop somewhere in the left half, leaving the right half sorted.
Find it in the wrapped list
nums is a list of different whole numbers that was sorted from smallest to largest and then rotated by moving some values from the front to the back (possibly none). Return the position of target in nums, or -1 if it isn't there.
nums = [4, 5, 6, 7, 0, 1, 2], target = 0 → 4
1 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000 · all values different