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 a target value target to search for in this rotated array nums. If target exists, then return its index; otherwise, return -1.

You must write an optimized 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 using binary search. However, a standard binary search won't work because the array is rotated. We need to adapt the binary search to handle the rotation.

Here's the strategy:

1. Find the Pivot: The pivot is the smallest element in the rotated array. It's the point where the array "breaks" from sorted order. We can find this using a modified binary search. Observe that the pivot element will always be smaller than the element at the end of the array.

2. Binary Search in the Correct Half: Once we find the pivot, we know which half of the array is sorted. We can then perform a standard binary search within the correct sorted half to find the target.

Detailed Algorithm:

1. Initialize left and right pointers: left = 0, right = nums.size() - 1.
2. Find the Pivot (modified binary search):
   • While left < right:
     • mid = (left + right) / 2
     • If nums[mid] > nums[right]: // Pivot is in the right half
       • left = mid + 1
     • Else: // Pivot is in the left half or mid is the pivot
       • right = mid
3. Determine which half is sorted:
   • After the loop, left will point to the pivot. The sorted half will be either nums[0...left-1] or nums[left...nums.size()-1].
4. Perform Binary Search:
   • If target falls within the sorted range, perform a standard binary search in that range.
   • Otherwise, the target is not in the array, return -1.

Code (C++)

#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        // Find the pivot
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // Determine which half to search
        int pivot = left;
        if (target >= nums[0] && target < nums[pivot]) {
            left = 0;
            right = pivot - 1;
        } else {
            left = pivot;
            right = nums.size() - 1;
        }

        // Binary search in the correct half
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // Target not found
    }
};

Complexity

• Time Complexity: O(log n). Both the pivot finding and the binary search steps have logarithmic time complexity.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.