# Search in Rotated Sorted Array

#### Question

Suppose an array sorted in ascending order 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`. Assume no duplicates. Require runtime in the order of O(logN).

#### Example

``````Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4``````
``````Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1``````

#### Solution

Binary Search.
In the given example, there are seven ways to rotate the array, as shown below. The bold part means a sorted part.

0　　1　　2　　 4　　5　　6　　7

7　　0　　1　　 2　　4　　5　　6

6　　7　　0　　 1　　2　　4　　5

5　　6　　7　　 0　　1　　2　　4

4　　5　　6　　7　　0　　1　　2

2　　4　　5　　6　　7　　0　　1

1　　2　　4　　5　　6　　7　　0

The key question here is how to know whether to continue searching in the left part or in the right part. We notice the bold part is always sorted. This means we can compare the middle number with the rightmost number to know if this is the bold part. If mid < right, then the right part is sorted. Otherwise, the left part is sorted, so this is how we differentiate these two cases.

The next step is to check if the target is in this sorted range. If so, we limit the range and keep searching in this range in the next loop. If not, we limit the range to the other part and continue searching. The loop is terminated until the target is found.

``````class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:    # Use "<=" instead of "="
mid = right + (right - left) >> 1
if nums[mid] == target:
return mid
elif nums[mid] < nums[right]:
if nums[left] <= target <= nums[mid]:    # left is sorted
right = mid - 1
else:                                    # right is sorted
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:   # right is sorted
left = mid + 1
else:                                    # left is sorted
right = mid - 1
return -1``````