## Description

https://leetcode.com/problems/search-in-rotated-sorted-array/

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`

.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of *O*(log *n*).

**Example 1:**

Input:nums = [`4,5,6,7,0,1,2]`

, target = 0Output:4

**Example 2:**

Input:nums = [`4,5,6,7,0,1,2]`

, target = 3Output:-1

## Explanation

find the rotation point and then do binary search

## Python Solution

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
result = -1
if nums == None or len(nums) == 0:
return -1
min_index = self.find_min_index(nums)
if nums[min_index] <= target <= nums[-1]:
return self.binary_search(nums, target, min_index, len(nums) - 1)
return self.binary_search(nums, target, 0, min_index)
def find_min_index(self, nums):
start = 0
end = len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if nums[mid] < nums[end]:
end = mid
else:
start = mid
if nums[start] < nums[end]:
return start
return end
def binary_search(self, nums, target, start, end):
while start + 1 < end:
mid = start + (end - start) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
start = mid
else:
end = mid
if nums[start] == target:
return start
elif nums[end] == target:
return end
return -1
```

- Time complexity: O(N).
- Space complexity: O(1).

I found that solution is very popular and helpful : https://www.youtube.com/watch?v=Z76IRo_vV0s