Binary search on a sorted list someone rotated

A sorted list of distinct numbers has been rotated: some number of values were taken off the front and put on the end. Find the position of a target, or -1 if it is not there.

Worked example#

[4, 5, 6, 7, 0, 1, 2] is [0, 1, 2, 4, 5, 6, 7] rotated. Looking for 0 gives position 4. Looking for 3 gives -1.

The idea#

The list is not sorted, so a plain binary search is wrong. But it is not arbitrary either, and the structure is the key:

Cut the list anywhere. At least one of the two halves is properly sorted.

That has to be true, because there is only one place where the order breaks, and it can only fall in one half.

So at each step, work out which half is sorted, and then you can ask the ordinary question about it: is the target inside that half's range? If it is, search there. If it is not, search the other half, even though you know less about it, because a step later the same argument applies again.

if nums[low] <= nums[mid]:                # the left half is sorted
    if nums[low] <= target < nums[mid]:   # and the target is inside it
        search left
    else:
        search right
else:                                     # then the right half is sorted
    if nums[mid] < target <= nums[high]:
        search right
    else:
        search left

Still halving each time, so still log n.

The comparisons that matter#

Note where the boundaries are inclusive. nums[low] <= target includes the low end because nums[low] is a real candidate; target < nums[mid] excludes the middle because you have already checked it. Getting one of those backwards produces a search that works on most inputs and misses an element at an edge, which is the worst kind of wrong.

Worth testing against: a target at position 0, a target at the last position, and a list rotated by zero, which is just a sorted list.

Constraints#

• 1 <= n <= 100000, values distinct
• The list is a sorted sequence rotated left by some amount, possibly zero