Python solution with detailed explanation


  • 0
    G

    Solution

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

    Algorithm

    • 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
    

Log in to reply
 

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