CA 20 - Search in Rotated Sorted Array

Problem

Given a sorted array nums that is rotated at an unknown index and a target value, the task is to find the index of the target.

If the target is not present, return -1.

The solution must have O(log n) time complexity.

Output

Example 1
Output: 4
Example 2
Output: -1
Example 3
Output: -1

My Approach

To solve this problem, I used a modified Binary Search.

I set two pointers left and right.

In each step, I calculate the middle index.

Then I check which part of the array is sorted:

If the left half is sorted:
Check if the target lies in this range
If yes, move to the left half
Otherwise, move to the right half
If the right half is sorted:
Check if the target lies in this range
If yes, move to the right half
Otherwise, move to the left half

I repeat this process until I find the target or exhaust the search space.

This works because at least one half of the rotated array is always sorted.

This approach is efficient because:

It reduces the search space logarithmically
It uses constant extra space
Code

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