Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return 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

Example 3:

Input: nums = [1], target = 0 Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

Approach: Modified Binary Search

Algorithm

1. Use binary search with lo and hi
2. Determine which half is sorted by comparing nums[mid] with nums[lo]
3. If the left half is sorted, check whether target lies in [nums[lo], nums[mid]]; if so search left, otherwise search right
4. Otherwise the right half is sorted; check whether target lies in [nums[mid], nums[hi]]; if so search right, otherwise search left
5. Return the index when found, or -1

Time & Space Complexity

• Time Complexity: O(log n) - halving the search range each step
• Space Complexity: O(1) - iterative binary search

Java Implementation

public class SearchInRotatedSortedArray {

    /**
     * Search for target in a possibly rotated sorted array.
     * @param nums Rotated sorted array with distinct values
     * @param target Value to find
     * @return Index of target or -1
     */
    public static int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

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

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

        return -1;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Input: nums = [4,5,6,7,0,1,2], target = 0");
        System.out.println("Output: " + search(nums1, 0)); // Expected: 4

        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Input: nums = [4,5,6,7,0,1,2], target = 3");
        System.out.println("Output: " + search(nums2, 3)); // Expected: -1

        int[] nums3 = {1};
        System.out.println("Input: nums = [1], target = 0");
        System.out.println("Output: " + search(nums3, 0)); // Expected: -1
    }
}

Example Walkthrough

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

1. lo=0, hi=6, mid=3 (value 7). Left half [4,5,6,7] is sorted. target=0 not in [4,7]. Search right: lo=4
2. lo=4, hi=6, mid=5 (value 1). Left half [0,1] is sorted (0 <= 1). target=0 in [0,1]. Search left: hi=4
3. lo=4, hi=4, mid=4 (value 0). Found at index 4.

Key Points

1. One Half Is Always Sorted: Comparing nums[mid] with nums[lo] identifies the sorted segment
2. Distinct Values: No duplicates, so strict comparisons are safe
3. O(log n) Requirement: Binary search must not be replaced with a linear scan
4. Rotated Detection: The check nums[lo] <= nums[mid] handles the rotation boundary
5. Edge Cases: A single-element array and a non-rotated array both work