LeetCode 33 – Search in Rotated Sorted Array

A rotated sorted array is not sorted, so binary search should not work on it. It does, because of one structural fact: however you cut a rotated array in half, at least one of the halves is properly sorted. Find out which, and you can decide in O(1) whether the target lives there.

The problem

An ascending array was rotated at some unknown pivot — [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]. Find a target's index, or -1. No duplicates, and the runtime must be O(log n).

[4,5,6,7,0,1,2], target = 0  ->  4
[4,5,6,7,0,1,2], target = 3  -> -1
[1],             target = 0  -> -1
[3,1],           target = 1  ->  1

The O(log n) requirement is doing real work here. It rules out the linear scan, which is otherwise a perfectly good answer to "find a value in an array".

The one fact that makes it work

A rotated sorted array has exactly one break point — the place where a large value is followed by a small one. Pick any midpoint and the break is on one side of it or the other. The side without the break is a plain ascending run.

[4, 5, 6, 7, 0, 1, 2]        mid = 7
 └──sorted──┘  └─has break─┘   left half is ordinary

[6, 7, 0, 1, 2, 4, 5]        mid = 1
 └─has break─┘  └─sorted─┘     right half is ordinary

Telling them apart is a single comparison: nums[lo] <= nums[mid] means the left half is sorted, because a break between them would have put a smaller value at mid.

Once you know which half is sorted, membership in it is two comparisons against its endpoints — that is the only thing sortedness is being used for. If the target is inside that range, search there; otherwise search the other half, which is where the break is and where the same reasoning applies again one level down.

The <= rather than < matters when the window narrows to two elements and lo == mid. A single element is trivially sorted, and with a strict comparison that case falls into the wrong branch.

Java

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;

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

        return -1;
    }
}

The range checks exclude nums[mid] — it was already tested for equality on the line above, so including it would only re-examine a known non-match. The endpoints nums[lo] and nums[hi] are included, because they have not been.

lo + (hi - lo) / 2 is the overflow-safe midpoint. Writing (lo + hi) / 2 by habit is the bug that sat undetected in java.util.Arrays.binarySearch and in countless textbooks until 2006.

Python

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1

        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid

            if nums[lo] <= nums[mid]:                       # left half is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:                                           # right half is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1

        return -1

Python's chained comparison writes the range check the way it reads on paper, and evaluates target once.

The two-pass alternative, and why not to write it

You can binary search for the break point first, then binary search the correct half normally. It is O(log n) too and it is easier to reason about, which is a real argument in its favour.

It is also twice the code and twice the surface for off-by-one errors, and it needs its own care about which half to pick and whether the array was rotated at all. The single-pass version is the one interviewers are looking for. Mention the two-pass idea if you get stuck — arriving at a correct two-pass solution beats an incorrect one-pass solution every time.

Complexity

O(log n) time, O(1) space. The window halves on every iteration exactly as in ordinary binary search; the rotation only changes which half is discarded, never how many.

The duplicates follow-up

Search in Rotated Sorted Array II (81) allows duplicates, and it breaks this algorithm in a specific way. With [1, 0, 1, 1, 1], nums[lo], nums[mid] and nums[hi] are all 1, and the comparison can no longer tell which side is sorted — the information simply is not there.

The repair is to shrink the window by one (lo++) when nums[lo] == nums[mid] and make no other decision. That degrades the worst case to O(n), and it is provably unavoidable: an array of all 1s with a single 0 hidden in it cannot be searched faster than linearly, because no comparison narrows anything. Knowing why it degrades is the answer they want.

What the interviewer is checking

That you spot that one half is always sorted, rather than trying to locate the rotation first.
That the sorted-half test uses <=, and that you can say what breaks with <.
Single-element and two-element arrays, where lo, mid and hi collide.
A zero-rotation array — still sorted, and it must not be a special case.
The overflow-safe midpoint.
That you know duplicates break it, and why the fix is O(n).