Search an Element in a Rotated Sorted Array

A rotated sorted array is not sorted, so binary search cannot be applied as written. It can be adapted, because of one property: at least one half of any split is still sorted, and deciding which one takes a single comparison.

Written against Java 17.

The problem

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

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

The array was sorted, then rotated at an unknown pivot. Find the index of the target in O(log n).

The one-pass solution

static int search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

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

        if (nums[low] <= nums[mid]) {
            // the LEFT half is sorted
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1;          // target is inside the sorted left half
            } else {
                low = mid + 1;
            }
        } else {
            // the RIGHT half is sorted
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;           // target is inside the sorted right half
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

O(log n) time, O(1) space, and no pre-pass to find the pivot.

Why nums[low] <= nums[mid] identifies the sorted half

The rotation point is the single place where an element is smaller than its predecessor. It lies in exactly one half of any split, and the other half is therefore an unbroken ascending run.

If nums[low] <= nums[mid], the left half contains no descent, so it is sorted. Otherwise the descent is somewhere in the left half, and the right half must be the sorted one.

The <= rather than < matters when low == mid, which happens on a two-element range. With <, a range of [3, 1] would classify the left half as unsorted and take the wrong branch.

Why the range tests need both bounds

Having identified the sorted half, the question is whether the target lies inside it. That is two comparisons, not one:

if (nums[low] <= target && target < nums[mid])

Both are necessary. Testing only target < nums[mid] would send a target smaller than everything in the left half into that half, where it is not. Testing only nums[low] <= target would send a target larger than nums[mid] there for the same reason.

The asymmetry of the inclusivity is deliberate too. nums[low] <= target includes the left end, because nums[low] has not been examined. target < nums[mid] excludes the midpoint, because nums[mid] was compared to the target on the line above and did not match. Including it would re-examine a known miss and, when low and mid are adjacent, stop the range from shrinking.

The right-hand branch mirrors it: nums[mid] < target excludes the already-checked midpoint, and target <= nums[high] includes the unexamined right end.

Getting one of those four boundaries wrong produces a solution that works on most inputs and fails at the pivot or at the array ends, which is why the exhaustive test below is worth more than a handful of hand-picked cases.

Tracing it

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

low	high	mid	nums[mid]	sorted half	target in it?	action
0	6	3	7	left (4 ≤ 7)	0 is not in 4..7	low = 4
4	6	5	1	left (0 ≤ 1)	0 is in 0..1	high = 4
4	4	4	0	—	match	return 4

Three iterations. Note that the “left half” at the second step is [0, 1] — the sorted-half test is relative to the current range, not to the whole array.

The two-pass alternative

Find the pivot first, then run an ordinary binary search on the correct side:

static int searchTwoPass(int[] nums, int target) {
    int pivot = findMinIndex(nums);          // the rotation point

    if (pivot == 0) return binarySearch(nums, 0, nums.length - 1, target);

    if (target >= nums[0]) return binarySearch(nums, 0, pivot - 1, target);
    return binarySearch(nums, pivot, nums.length - 1, target);
}

Two O(log n) passes, so the same complexity with a larger constant. It is easier to reason about and easier to get right, because each piece is a textbook routine — findMinIndex is the minimum-in-a-rotated-array loop.

Worth choosing when the array is searched many times, since the pivot can be computed once and cached. The one-pass version is better when each array is searched once.

Duplicates

static boolean searchWithDuplicates(int[] nums, int target) {
    int low = 0, high = nums.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return true;

        if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
            low++;                 // ambiguous — shrink from both ends
            high--;
        } else if (nums[low] <= nums[mid]) {
            if (nums[low] <= target && target < nums[mid]) high = mid - 1;
            else                                          low = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[high]) low = mid + 1;
            else                                            high = mid - 1;
        }
    }
    return false;
}

When nums[low], nums[mid] and nums[high] are all equal, the comparison carries no information: [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1] look identical at those three positions and have their pivot on opposite sides. The only safe move is to discard one element from each end.

That makes the worst case O(n) — [1, 1, 1, 1, 1, 0] degenerates completely. It is a proven lower bound, not an implementation weakness.

The return type also changes to boolean, because with duplicates “the index” is not well defined.

Note the ordering of the three branches. The ambiguity check must come first: if it ran after the sorted-half test, an all-equal window would take the left branch, conclude the left half is sorted, and discard the half that holds the target. The uninformative case has to be recognised before any conclusion is drawn from it.

Testing it exhaustively

The boundary conditions are the hard part, and they are cheap to verify completely at small sizes:

for (int n = 1; n <= 10; n++) {
    int[] base = IntStream.range(0, n).toArray();
    for (int k = 0; k < n; k++) {
        int[] rotated = rotate(base, k);
        for (int t = -1; t <= n; t++) {
            int idx = search(rotated, t);
            if (t < 0 || t >= n) assertEquals(-1, idx);
            else                 assertEquals(t, rotated[idx]);
        }
    }
}

Every rotation of every array up to length 10, and every target including two that are absent. It runs in milliseconds and catches all four boundary mistakes; a test with three hand-written arrays catches roughly none of them.

More in the algorithms guides.

Frequently asked questions

Why can’t I use a plain binary search?

The array is not sorted, so a comparison against the midpoint does not tell you which half to discard. The adaptation restores that by first identifying which half is sorted.

How does one comparison identify the sorted half?

The rotation point lies in exactly one half. If nums[low] <= nums[mid] there is no descent on the left, so the left half is sorted; otherwise the right half is.

Why <= and not < in that test?

When the range has two elements, low == mid, and < would misclassify the half.

Why do the range tests need two comparisons?

One bound alone admits targets outside the sorted half. Both bounds together are what confine the search correctly.

Why is one bound inclusive and the other exclusive?

The midpoint was already compared and did not match, so it is excluded; the outer end has not been examined, so it is included.

One-pass or two-pass?

One pass for a single search — same complexity, smaller constant. Two passes when the same array is searched repeatedly and the pivot can be cached.

What is the complexity with duplicates?

O(n) in the worst case. When the three sampled values are equal the comparison is uninformative and the only safe move is to shrink by one at each end.

Why does the duplicate version return a boolean?

With repeated values there is no single well-defined index for the target, so membership is the meaningful answer.

Does this work on an unrotated array?

Yes. The left half always tests as sorted and the algorithm degenerates to an ordinary binary search.

How should I test it?

Exhaustively over every rotation of every small array and every target, including absent ones. The failures in this problem are all at boundaries that hand-picked cases miss.