33. Search in Rotated Sorted Array

Intuition

The input array is sorted but rotated at an unknown pivot. To search efficiently in O(log n)

• We identify the pivot (i.e., the index of the largest element).

• The array can be split into two sorted halves: from 0 to pivot and from pivot+1 to n-1.

• Depending on the target, we perform binary search in the correct half.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

// Helper method to find the index of the pivot (maximum element)
int findPivotIndex(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        // Check if mid is the pivot (greater than both neighbors)
        boolean isGreaterThanLeft = (mid - 1 < 0 || nums[mid] > nums[mid - 1]);
        boolean isGreaterThanRight = (mid + 1 >= nums.length || nums[mid] > nums[mid + 1]);

        if (isGreaterThanLeft && isGreaterThanRight) {
            return mid;
        }

        // If mid is less than last element, pivot is on the left
        if (nums[mid] < nums[nums.length - 1]) {
            right = mid - 1;
        } else {
            left = mid + 1; // Pivot is on the right
        }
    }

    return -1; // Should never happen if array is rotated correctly
}

public int search(int[] nums, int target) {
    int resultIndex = -1;

    // Case 1: Array is not rotated (already sorted)
    if (nums[0] <= nums[nums.length - 1]) {
        resultIndex = Arrays.binarySearch(nums, target);
        return resultIndex < 0 ? -1 : resultIndex;
    }

    // Step 1: Find pivot index
    int pivotIndex = findPivotIndex(nums);

    // Step 2: Decide which half to search based on target
    if (target >= nums[0] && target <= nums[pivotIndex]) {
        // Target is in the left sorted portion
        resultIndex = Arrays.binarySearch(nums, 0, pivotIndex + 1, target);
    } else {
        // Target is in the right sorted portion
        resultIndex = Arrays.binarySearch(nums, pivotIndex + 1, nums.length, target);
    }

    return resultIndex < 0 ? -1 : resultIndex;
}