Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
If we observe the array carefully, we can split the array to: (1)sorted part and (2)rotated/pivot part. In the above example, by applying the usual binary search algorithm approach, we would get mid=7. From here, we can see that the first half is sorted and the second half is rotated, then check which part does the target value exist in. The code is as below:
def search_rotated(nums, target): l, r = 0, len(nums)-1 while l<=r: mid = (l+r)/2 if nums[mid] == target: return mid # first half is sorted if nums[l] <= nums[mid]: if nums[l] <= target < nums[mid]: # here the mid is not inclusive since we have the mid case at top r = mid-1 else: l = mid+1 # second half is sorted else: if nums[mid] < target <= nums[r]: l = mid+1 else: r = mid-1 return -1