Problem Statement in English

You’re given an integer array nums sorted in ascending order (with distinct values), and an integer target. Suppose that nums is rotated at some pivot unknown to you beforehand. You need to search for target in nums and return its index if it exists, or -1 if it does not exist.

Approach

We use a modified binary search to find the target in the rotated sorted array.

The key idea is to determine which half of the array is normally sorted and then decide whether to search in that half or the other half based on the target’s value. And then just rinse and repeat until we find the target or exhaust the search space.

And we’re done!

Solution in Python



class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            # Case 1: The left half is normally sorted
            if nums[left] <= nums[mid]:
                # Check if the target lies within this sorted left half
                if nums[left] <= target < nums[mid]:
                    right = mid - 1  # Search left
                else:
                    left = mid + 1   # Search right
            
            # Case 2: The right half must be normally sorted
            else:
                # Check if the target lies within this sorted right half
                if nums[mid] < target <= nums[right]:
                    left = mid + 1   # Search right
                else:
                    right = mid - 1  # Search left

        return -1

Complexity

  • Time: $O(\log n)$
    Since we are performing a binary search, which divides the search space in half at each step.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space for the pointers and variables.

Mistakes I Made

I had to look this up :(

And we are done.