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 (containing n unique elements) and an integer target. Write a function to determine if target exists in nums. If target is found in nums, 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

The key to solving this problem efficiently is to leverage the fact that the array is sorted, even if it's rotated. We can use a modified binary search to find the target. The modification lies in determining which half of the array is sorted and adapting our search accordingly.

1. Binary Search Setup: Initialize left = 0 and right = nums.length - 1.
2. Iteration: While left <= right:
   • Calculate mid = (left + right) / 2.
   • Check if nums[mid] is the target: If it is, return mid.
   • Determine which half is sorted:
     • If nums[left] <= nums[mid] (left half is sorted):
       • If target is within the range [nums[left], nums[mid]], search the left half (right = mid - 1).
       • Otherwise, search the right half (left = mid + 1).
     • Else (right half is sorted):
       • If target is within the range [nums[mid], nums[right]], search the right half (left = mid + 1).
       • Otherwise, search the left half (right = mid - 1).
3. Target Not Found: If the loop completes without finding the target, return -1.

Explanation

The algorithm works because it cleverly exploits the sorted nature of the two subarrays created by the rotation. By checking which half is sorted, we can efficiently eliminate one half of the search space in each iteration, mimicking the behavior of a standard binary search. The condition nums[left] <= nums[mid] identifies if the left half is sorted; otherwise, the right half must be sorted. The subsequent checks for target within each sorted subarray allow for the narrowing down of the search space.

Code (Java)

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 potential overflow

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

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

        return -1; // Target not found
    }
}

Complexity

• Time Complexity: O(log n) - Because we are using a modified binary search, the time complexity is logarithmic with respect to the input array size.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size. It's an in-place algorithm.