CA 20 - Search in Rotated Sorted Array

Problem
Search in Rotated Sorted Array
You are given a sorted array nums[] with distinct elements, but it may be rotated at an unknown index.

Your task is to find the index of a given target.
If the target is not present, return -1.

You must solve this in O(log n) time.

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

Approach

This is a modified Binary Search problem.

Even though the array is rotated, at least one half of the array is always sorted.

Steps:

• Initialize left and right pointers
• Find the middle element
• Check which half is sorted:
• If left half is sorted:
• Check if target lies in this range
• Otherwise, right half must be sorted:
• Check if target lies there
• Narrow down the search accordingly

Repeat until the target is found or the search space is exhausted.

Complexity:
Time Complexity: O(log n)
Space Complexity: O(1)

def search(nums, target):
    left, right = 0, 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
nums = [4,5,6,7,0,1,2]
target = 0
print(search(nums, target))