33. Search in Rotated Sorted Array

A rotated sorted array looks like it broke binary search — the array isn’t globally sorted anymore. The trick is that it’s still sorted in halves, and at every step one half is fully ordered. Find that half, and binary search still works in $O(\log n)$.

Question

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.

• Example1

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

• Example2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

• Example3

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

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

Answer: Binary Search

• Time Complexity: $O(logn)$
• Space Complexity: $O(1)$

public int searchInRotatedSortedArray(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

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

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

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

    return -1;
}

How the code picks the sorted half

Every iteration makes one decision: which side of mid is the ordered one. The test is nums[left] <= nums[mid] — if the left value is no bigger than the middle, the left half has no rotation seam in it, so it’s sorted; otherwise the seam is on the left and the right half is the sorted one.

Once you know which half is sorted, you can ask a clean range question about it:

• Left half sorted — is nums[left] <= target < nums[mid]? If yes, the target can only be in that range, so move right. If no, it’s in the messy half, so move left.
• Right half sorted — mirror it: is nums[mid] < target <= nums[right]? If yes, move left; otherwise move right.

The = in nums[left] <= nums[mid] matters. It covers the two-element window where left == mid, and dropping it sends single-step ranges down the wrong branch — a classic off-by-one that passes the easy tests and fails on inputs like [3,1].

Key Idea

• At first glance, a rotated sorted array may appear unsorted, making binary search seem inapplicable. However, at any step, at least one half of the array is always sorted.
• This property lets us eliminate half of the search space each iteration, preserving the $O(\log n)$ time complexity.
• There’s no need to explicitly find the rotation pivot — a single binary search loop solves it. Finding that pivot on its own is a sibling problem, Find Minimum in Rotated Sorted Array.

References

• https://leetcode.com/problems/search-in-rotated-sorted-array/