Search in Rotated Sorted Array — Half-Sorted Binary Search [LC 33, Google, Amazon]

Problem Statement#

LeetCode 33 — Search in Rotated Sorted Array · Difficulty: Medium

There is an integer array nums sorted in ascending order with distinct values. Before the function is called, nums is possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

Given the array nums and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

Constraints:

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

Example 1:

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 is at index 4.

Example 2:

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 does not exist in the array.

Example 3:

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

Why This Problem Matters#

LC 33 is one of the most frequently asked binary search problems in FAANG interviews. Google, Amazon, and Meta include it in phone screens and onsite rounds because it probes a candidate's ability to extend a well-known algorithm to a subtly broken structure.

A rotated sorted array looks sorted locally but has a single discontinuity — the rotation point. Naive binary search fails on it because the middle element can no longer tell you "everything to my right is larger." The challenge forces you to reason one level deeper: not "is the target in the right half?" but "which half is guaranteed sorted, and does the target lie in that sorted half?"

This distinction — identifying and exploiting a locally sorted segment — reappears in dozens of harder problems: finding the minimum in a rotated array (LC 153), handling duplicates (LC 81), searching a 2D matrix (LC 74), and even certain segment tree queries. Mastering LC 33 is mastering the building block.

In practice, interviewers also use this problem to test clarity of thought under pressure. The algorithm has four branches. Getting all four right on the first try, while explaining your invariant aloud, is the benchmark.

The Core Insight#

A rotation splits the array into two sorted halves. At any mid, one of the two halves is always fully sorted. That is the key fact.

If the left half [lo, mid] is sorted — which is the case when nums[lo] <= nums[mid] — you can check in O(1) whether target lies within [nums[lo], nums[mid]). If yes, narrow right. If no, search the right half.

If the left half is not sorted, then the right half [mid, hi] must be sorted. Check whether target lies within (nums[mid], nums[hi]]. If yes, narrow left. If no, search the left half.

This single observation lets you eliminate half the array at every step, preserving O(log n).

The invariant you maintain throughout: if target exists in nums, it lies within [lo, hi].

Visual Dry Run#

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

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

Common Mistakes#

1. Treating both halves as sorted. The most common mistake is forgetting that the rotation makes one half unsorted. Applying classic binary search directly gives wrong answers for rotated inputs.

2. Using < instead of <= for the left-half sorted check. The condition must be nums[lo] <= nums[mid] (with <=), not nums[lo] < nums[mid]. When lo == mid (single-element range), nums[lo] == nums[mid] and the left half is trivially sorted — the <= catches this.

3. Wrong boundary in the target range check. When checking whether target falls in the sorted left half, the condition is nums[lo] &lt;= target < nums[mid] — strict < on the mid side. If you accidentally use <=, you double-count nums[mid] and may skip elements.

4. Forgetting to handle the nums[mid] == target check first. You must return immediately when nums[mid] == target. If you enter the half-selection logic first, you may incorrectly move lo or hi past the answer.

5. Getting the two else branches backwards. After identifying which half is sorted, the else of each branch must search the opposite (unsorted) half. Swapping them causes the search to always move in the wrong direction.

6. Using open-interval template with this problem. The while lo < hi template requires different boundary updates. Mixing it with the while lo <= hi template — using hi = mid in one place and hi = mid - 1 in another — causes subtle infinite loops or skipped elements.

Solutions#

Python#

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1          # inclusive bounds [lo, hi]
 
    while lo <= hi:                      # loop while search space is non-empty
        mid = lo + (hi - lo) // 2       # safe midpoint: avoids integer overflow
 
        if nums[mid] == target:          # found the target — return immediately
            return mid
 
        # Determine which half is sorted.
        # Because all values are distinct, nums[lo] <= nums[mid] means
        # the entire left segment [lo..mid] is sorted (no rotation in it).
        if nums[lo] <= nums[mid]:        # left half [lo, mid] is sorted
            if nums[lo] <= target < nums[mid]:
                # target falls within the sorted left half
                hi = mid - 1            # discard right half
            else:
                # target is NOT in the sorted left half; must be in right
                lo = mid + 1            # discard left half
 
        else:                            # right half [mid, hi] is sorted
            if nums[mid] < target <= nums[hi]:
                # target falls within the sorted right half
                lo = mid + 1            # discard left half
            else:
                # target is NOT in the sorted right half; must be in left
                hi = mid - 1            # discard right half
 
    return -1                            # target not found

JavaScript#

function search(nums, target) {
    let lo = 0;
    let hi = nums.length - 1;           // inclusive upper bound
 
    while (lo <= hi) {                   // loop while search space is non-empty
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
        if (nums[mid] === target) {      // exact match — return index immediately
            return mid;
        }
 
        // Check which half is sorted.
        // Left half [lo..mid] is sorted when nums[lo] <= nums[mid].
        if (nums[lo] <= nums[mid]) {     // left half is sorted
            if (nums[lo] <= target && target < nums[mid]) {
                // target lies in the sorted left half
                hi = mid - 1;           // search left
            } else {
                // target is outside the sorted left half — search right
                lo = mid + 1;
            }
        } else {                         // right half [mid..hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) {
                // target lies in the sorted right half
                lo = mid + 1;           // search right
            } else {
                // target is outside the sorted right half — search left
                hi = mid - 1;
            }
        }
    }
 
    return -1;                           // search space exhausted, not found
}

Complexity Analysis#

Each iteration of the while loop discards at least half the remaining search space. After at most ceil(log₂(n)) iterations, either the target is found or lo > hi. For n = 5000, that is at most 13 iterations. Space is O(1) — only lo, hi, and mid are used.

Follow-up Questions#

Q: What if the array contains duplicates? That is LC 81. Duplicates create an ambiguous case where nums[lo] == nums[mid] doesn't tell you which half is sorted. The fix: increment lo by 1 to eliminate one duplicate, degrading worst-case to O(n).

Q: How do you find the rotation pivot index? Binary search on the minimum element (LC 153). Compare nums[mid] with nums[hi]; if nums[mid] > nums[hi], the pivot is in the right half.

Q: Can you first find the pivot, split, then binary search each half? Yes — two-pass approach. Find pivot in O(log n), then binary search the appropriate half. Same asymptotic complexity, but two passes instead of one. The single-pass approach above is preferred.

Q: What if the array was not rotated at all? The algorithm handles it correctly. When there is no rotation, nums[lo] <= nums[mid] is always true and the left half is always sorted — identical to classic binary search.

This Pattern Solves#

• LC 33 — Search in Rotated Sorted Array (this problem)
• LC 81 — Search in Rotated Sorted Array II (with duplicates)
• LC 153 — Find Minimum in Rotated Sorted Array
• LC 154 — Find Minimum in Rotated Sorted Array II
• Any problem where the input is "almost sorted" with a single discontinuity

Key Takeaway#

In a rotated sorted array, one of the two halves is always fully sorted. Check which one using nums[lo] <= nums[mid], then test whether the target falls in that sorted range. If yes, search there. If no, search the other half. This single observation preserves O(log n) despite the rotation. Every time you see a rotated or "almost sorted" array in an interview, reach for this template first.

Key Takeaways#

• LC 33 is one of the most common binary search interview problems at Google, Amazon, and Meta — expect it in phone screens and onsites.
• A rotated sorted array always has one fully sorted half at every midpoint; identifying which one is the entire algorithm.
• Use nums[lo] <= nums[mid] (with <=) to determine whether the left half is sorted — the = handles the single-element case.
• When the left half is sorted, check nums[lo] <= target < nums[mid]; when right is sorted, check nums[mid] < target <= nums[hi].
• Handle nums[mid] == target first with an immediate return before the half-selection logic executes.
• An unrotated array is a valid special case — the algorithm handles it without any extra code.
• The pattern generalises to LC 81 (duplicates), LC 153 (find minimum), and LC 154 (find minimum with duplicates).