# Python solution with detailed explanation

• 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.