Search in Rotated Sorted Array medium

Problem Statement

Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values), and a target value.

Suppose that nums is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You must write an efficient algorithm to search target in nums. If target is found, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1

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

Example 2

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

Steps and Explanation

This problem leverages binary search. The key is understanding that even though the array is rotated, each half of the array after a split in binary search will still be sorted. We use this property to intelligently decide which half to search.

1. Binary Search Setup: Initialize left and right pointers to the start and end of the array.

2. Iteration: While left <= right:

   • Calculate the middle index.
   • Check if target is at middle: If nums[middle] == target, return middle.
   • Check if left half is sorted: If nums[left] <= nums[middle]:
     • If target is within the range of the sorted left half (nums[left] <= target < nums[middle]), search the left half (right = middle - 1).
     • Otherwise, search the right half (left = middle + 1).
   • Check if right half is sorted: Otherwise (meaning the right half is sorted):
     • If target is within the range of the sorted right half (nums[middle] < target <= nums[right]), search the right half (left = middle + 1).
     • Otherwise, search the left half (right = middle - 1).

3. Target Not Found: If the loop completes without finding the target, return -1.

Code

def search(nums, target):
    """
    Searches for a target value in a rotated sorted array using binary search.

    Args:
      nums: The rotated sorted array of integers.
      target: The integer value to search for.

    Returns:
      The index of the target value if found, otherwise -1.
    """
    left, right = 0, len(nums) - 1

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

        if nums[middle] == target:
            return middle

        # Check if left half is sorted
        if nums[left] <= nums[middle]:
            if nums[left] <= target < nums[middle]:
                right = middle - 1
            else:
                left = middle + 1
        # Otherwise, right half is sorted
        else:
            if nums[middle] < target <= nums[right]:
                left = middle + 1
            else:
                right = middle - 1

    return -1

Complexity

• Time Complexity: O(log n) due to the binary search algorithm.
• Space Complexity: O(1) because we use only a constant amount of extra space.