Search in Rotated Sorted Array medium

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 0 times.

You are given the rotated array nums (0-indexed) and an integer target.

Write a function that returns the index of target if it is in nums, or -1 if it is not in nums.

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

The key to solving this problem efficiently is to leverage the fact that the array is partially sorted. We can use a modified binary search approach. In each step, we compare the target with the middle element:

1. Check the middle element: If nums[mid] == target, we found it! Return mid.

2. Determine which half is sorted: We check if the left half (nums[left...mid-1]) is sorted or the right half (nums[mid+1...right]) is sorted. This can be done by comparing nums[left] and nums[mid].

3. Search the sorted half: If the target falls within the range of the sorted half, we search only that half. Otherwise, the target must be in the unsorted half, so we search there.

4. Repeat: Steps 1-3 are repeated until the target is found or the search space is exhausted.

Code (C#)

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid overflow

            if (nums[mid] == target) {
                return mid;
            }

            // Check if the left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1; // Target not found
    }
}

Complexity

• Time Complexity: O(log n) - We are effectively performing a binary search.
• Space Complexity: O(1) - We are using a constant amount of extra space. The algorithm is in-place.