A sorted list was rotated, yet binary search still works: one half is always in order, so check if the target sits there and drop the other.
▼The problem
LeetCode 33 (Medium). A sorted array of distinct integers was rotated at an unknown pivot (for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Given target, return its index, or −1 if it isn't there, in O(log n).
Examples (LeetCode's): nums = [4,5,6,7,0,1,2], target = 0 → 4 (the walkthrough: mids 3, 5, 4); target = 3 → −1; nums = [1], target = 0 → −1 (run through the code in scene 5).
The solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Transcript
Search in Rotated Sorted Array. A sorted list of distinct numbers was rotated at an unknown pivot, like a dial someone turned. Given a target, return its index, or minus one if it's missing, in log n time.
Take four, five, six, seven, zero, one, two. Target zero sits at index four. Target three isn't there, so minus one. And in a list of just one, zero is missing: minus one.
The simple way checks every number. That's order n, and it ignores that the list is almost sorted.
It's binary search, but the array has been turned. Split at the middle, and one half is always sorted. If the left end is at most the middle, the left half is sorted. Is the target inside that half's range? Search there. If not, search the other half.
In code, keep low and high. Take mid; if it's the target, return it. If the left half is sorted, and the target falls in it, move high below mid; else move low past mid. Otherwise the right half is sorted, so mirror the test. If the range empties, return minus one.
Walk it with target zero. Mid is seven. Four to seven is sorted, and zero isn't in it, so go right. Now mid is one. Zero to one is sorted and holds zero, so go left. Mid is zero: found at index four.
Each step halves the range: order log n time, and order one space.
Find the sorted half, test the target, halve again. That's Search in Rotated Sorted Array.