Search in Rotated Sorted Array

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.

My Solution

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
        l = mid+1
    # second half is sorted
      if nums[mid] < target <= nums[r]:
        l = mid+1
        r = mid-1
  return -1

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s