33. Search in Rotated Sorted Array 🔥

Medium

Problem:

Find the index of the target value in an array sorted by rotation around a specific pivot.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

https://leetcode.com/problems/search-in-rotated-sorted-array

Solution:

1. Find the smallest value and use its index as the pivot.

pivot = nums.index(min(nums)) # numpy.argmin()

1. Find the minimum value left and use it as the pivot. Based on this, move by the pivot's position to form mid_pivot' and then find the target value again using binary search.

2. When comparing the target and the values, use mid_pivot as the reference instead of mid, but move left and right based on mid.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        # Target: minimum value
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        pivot = left

        # Binary Search
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            mid_pivot = (mid + pivot) % len(nums)

            if nums[mid_pivot] < target:
                left = mid + 1
            elif nums[mid_pivot] > target:
                right = mid - 1
            else:
                return mid_pivot
            
        return -1