Python solution with detailed explanation


  • 1
    G

    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
    

Log in to reply
 

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