Search in Rotated Sorted Array

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

Solution 1

Use min-in-rorated-sorted-array to find the pivot, reconstruct the sorted array, then search in the array, with shifted index. Two binary-searches required.

Solution 2

Alternatively, use only one round of binary-search. Determine next step based on whether left or right subarray is sorted.

n = len(nums)
left, right = 0, n - 1
 
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] >= nums[left]:  # Left subarray is sorted
        if nums[mid] >= target >= nums[left]:
            right = mid
        else:
            left = mid + 1
    else:  # Right subarray is sorted
        if nums[mid] <= target <= nums[right]:
            left = mid + 1
        else:
            right = mid
    return left if nums[left] == target else -1