A rate-limiter stores client IDs in a sorted array. Overnight a compact-and-rotate job moved the physical start, so the smallest IDs now sit after a drop instead of at index 0. The first version still walked from slot 0. A few thousand clients returned instantly. After the fleet grew to two million IDs, lookups were still scanning when the request timed out.

One half of every window is still sorted; search the half that can hold the target. An array already gives a[i] for free. A scan uses that and still pays O(n). Rotation broke “the whole window is sorted.” It did not break “at least one of the two halves still is.”

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant, mid overflow, and miss encoding. The membership writeup is the unrotated case: discard the half that cannot hold the target. Here you first ask which half is still ordered, then apply the same discard.

The problem

An int[] nums was strictly increasing, then rotated at an unknown pivot — nums is a rotation of a sorted unique sequence. Given an int target, return the index i where nums[i] == target, or -1 if it is absent. Typical interviews want O(log n) time.

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

Note: If the array was never rotated, the left half of every window is sorted and this loop is ordinary binary search. If values can repeat, “which half is sorted” can lie when nums[lo] == nums[mid]. Uniqueness is the license for the O(log n) claim.

Linear scan is the honest brute force

Every index is compared once. Correct. Linear.

int searchLinear(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

At n = 20 this is a rounding error. At n in the millions you paid a full walk for a question a rotated range still answers in a handful of probes: which half is sorted, and can that half hold the target?

At mid, one half is still sorted

Keep inclusive bounds: lo and hi are valid indices. Mid is lo + (hi - lo) / 2. After a miss, at least one of [lo, mid] or [mid, hi] is a sorted slice. The rotation, if it exists, sits in the other half.

  • If nums[mid] == target, return mid.
  • If nums[lo] <= nums[mid], the left half is sorted. If nums[lo] <= target && target < nums[mid], the target lives there: hi = mid - 1. Otherwise lo = mid + 1.
  • Else the right half is sorted. If nums[mid] < target && target <= nums[hi], lo = mid + 1. Otherwise hi = mid - 1.

lo > hi means the invariant has nothing left. Return -1.

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

lo=0 hi=6 mid=3  nums[3]=7
  left [4, 5, 6, 7] sorted; 0 not in [4, 7]  → lo=4
lo=4 hi=6 mid=5  nums[5]=1
  left [0, 1] sorted; 0 in [0, 1]            → hi=4
lo=4 hi=4 mid=4  nums[4]=0  hit, return 4

The Java is that loop:

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;
        }
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Time is O(log n) — each comparison still throws away half the remaining range. Space is O(1) — two indices. The unrotated membership loop and mid overflow already live on the algorithms post; do not re-lecture them unless they ask.

Note: Test the left half with nums[lo] <= nums[mid], not a strict less-than. A singleton left (lo == mid) is sorted. Strict < can send you into the rotated half and miss a target that was sitting at lo.

What interviewers usually poke next

  • Duplicates. When values can repeat, nums[lo] == nums[mid] no longer proves the left half is ordered. You may have to shrink lo or hi by one, and the bound can degrade to linear. That is a different, harder problem; do not pretend this loop survives it.
  • Find the minimum. The minimum is a sibling question: same rotated layout, no target, halt when the window’s left is the smallest remaining value. Do not reuse this membership loop as a drop-in.
  • No rotation. nums[lo] <= nums[mid] stays true. The branch that searches the left range is ordinary binary search. Say that out loud so they know you did not special-case the pivot.
  • Empty / null. hi becomes -1, the loop never runs, return -1. In production you would reject null; at the board, ask.

You are done with this problem when you can say, out loud, why the linear scan is correct, why rotation leaves one sorted half at every mid, and why the target goes into that half only when it sits inside that half’s closed range.