Search in Rotated Sorted Array II https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
- Finding a pivot and then doing bsearch will not work in this scenario.
- The ideas follow from Find minimum in Rotated Sorted Array and Finding Minimum with Duplicates.
- If mid is target, then return.
- If right is sorted, then bounds are adjusted based on whether target is contained in it or not.
- If left is sorted, then bounds are adjusted based on whether target is contained in it or not.
- Add the condition for nums[mid] == nums[high]
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: bool """ low, high = 0, len(nums)-1 while low <= high: mid = low + int((high-low)/2) if nums[mid] == target: return True elif nums[mid] < nums[high]: if target >= nums[mid] and target <= nums[high]: low = mid + 1 else: high = mid - 1 elif nums[mid] > nums[high]: if target >= nums[low] and target <= nums[mid]: high = mid - 1 else: low = mid + 1 else: high = high-1 return False