33. Search in Rotated Sorted Array

Problem Link

This problem can be reduced into simple Binary search by solving it in two steps.

Since the array is a rotated version of a sorted array, the first task is to find the rotation point, or \(pivot\), which is the index of the smallest element. This has been solved in previous problem.

Once the \(pivot\) is found, the array can be viewed as two individually sorted subarrays, one from the \(pivot\) to the end, and one from the start to just before the \(pivot\). At this point, the problem becomes a standard binary search. You've to just determine which of these two sorted ranges could contain the \(target\):

• if \(nums[pivot] \le target \le nums[right]\), the \(target\) is in right segment from pivot
• otherwise, it's in left segment from pivot.

Finally, run a normal binary search on the chosen segment to find the target.

Runtime Complexity

Time: \(O(logn)\)

Space: \(O(1)\)

PythonGo

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = left + (right-left)//2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1

        pivot = left
        left, right =0, len(nums)-1
        if nums[pivot] <= target <= nums[right]:
            left = pivot
        else:
            right = pivot-1

        while left < right:
            mid = left + (right-left)//2
            if target <= nums[mid]:
                right = mid
            else:
                left = mid + 1
        if nums[left] == target:
            return left
        return -1

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    var mid int
    for left < right {
        mid = left + (right-left)/2
        if nums[mid] <= nums[right] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    pivot := left
    left, right = 0, len(nums)-1
    if nums[pivot] <= target && target <= nums[right] {
        left = pivot
    } else {
        right = pivot - 1
    }

    for left < right {
        mid = left + (right-left)/2
        if target <= nums[mid] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if nums[left] == target {
        return left
    }
    return -1
}

---