Search in Rotated Sorted Array

How it works

A rotated sorted array is really two sorted arrays stuck together.
So we break the problem into two simple binary searches:

1. First binary search:
   Find the pivot — the index of the smallest element.
   This tells us where the array was rotated.

2. Second binary search:
   Decide which sorted half may contain the target,
   then run a standard binary search only on that half.

Steps

1. Use binary search to locate the pivot:
   • Compare middle and right elements.
   • If nums[mid] > nums[right], the pivot is to the right.
   • Otherwise, it's to the left (including mid).
2. After finding the pivot:
   • If the target lies between nums[pivot] and the last element, search the right half.
   • Otherwise, search the left half.
3. Perform a standard binary search on the selected half.
4. Return the index if found, else -1.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Using Strict Inequality When Comparing with Left Element

In the one-pass binary search, the condition nums[l] <= nums[mid] uses <= rather than <. This handles the edge case when l == mid, which occurs in small subarrays. Using < instead can cause incorrect half selection and miss the target.

Confusing Pivot Finding with Target Finding

The two-pass approach requires finding the pivot first (smallest element), then searching the appropriate half. Do not conflate these steps. The pivot search uses nums[mid] > nums[r] to move left, while the target search is a standard binary search. Mixing the logic leads to wrong results.

Not Handling the Non-Rotated Array Case

When the array is not rotated (or rotated by 0), the pivot is at index 0. Your solution should still work correctly. Test with sorted arrays like [1, 2, 3, 4, 5] to ensure your pivot-finding logic returns index 0 and the subsequent search works.

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) // 2
            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m

        pivot = l
        l, r = 0, len(nums) - 1

        if target >= nums[pivot] and target <= nums[r]:
            l = pivot
        else:
            r = pivot - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1

        return -1

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

        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }

        int pivot = l;
        l = 0;
        r = nums.size() - 1;

        if (target >= nums[pivot] && target <= nums[r]) {
            l = pivot;
        } else {
            r = pivot - 1;
        }

        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return -1;
    }
};