**Solution**

**Search in Rotated Sorted Array** https://leetcode.com/problems/search-in-rotated-sorted-array/

**Find pivot/smallest element and then search**

- Find the pivot element - same method we used for finding minimum element without duplicates.
- Find what range the target element lies in and do binary search in that range.

```
class Solution(object):
def find_pivot(self, nums):
low,high = 0, len(nums)-1
while low < high:
mid = low + (high-low)//2
if nums[mid] > nums[high]:
low = mid + 1 # Note that mid+1 is important.
else:
high = mid
return low
def bsearch(self, nums, low, high, target):
while low <= high:
mid = low + int((high-low)/2)
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
high = len(nums)-1
pivot = self.find_pivot(nums)
if target >= nums[pivot] and target <= nums[high]:
return self.bsearch(nums, pivot, high, target)
else:
return self.bsearch(nums, 0, pivot-1, target)
```

**Use modified binary search**

- One half will be sorted and the other will not be sorted.
- Figure out which half is sorted. Figure out if the target lies in that region or not. Use this information to determine the regions to eliminate.

```
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
low, high = 0, len(nums)-1
while low <= high:
mid = low + (high-low)//2
if nums[mid] == target:
return mid
elif nums[mid] < nums[high]:
if target >= nums[mid] and target <= nums[high]:
low = mid + 1
else:
high = mid - 1
else:
if target >= nums[low] and target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
return -1
```