Search Rotated Array LeetCode 33 Deep Dive

LeetCode 33 gives you a sorted integer array that has been rotated at some unknown pivot index. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] after rotating at index 4. You are given a target value and must return its index in the rotated array, or -1 if it does not exist.

The naive approach — linear scan — works in O(n) but misses the point. The key constraint is that all elements are unique and the original array was sorted, so a modified binary search can still find the target in O(log n) time. The challenge is adapting binary search to handle the rotation without first finding the pivot.

This problem is a template for a family of rotated-array problems: find minimum in rotated sorted array, search in rotated sorted array II (with duplicates), and others. Mastering the core insight here unlocks the entire family.

The fundamental observation that makes this problem solvable in O(log n) is: after any rotation, when you pick a midpoint in a binary search window, at least one of the two halves — left half [lo, mid] or right half [mid, hi] — is guaranteed to be fully sorted in ascending order.

This is because a rotation creates at most one "break point" in the array where the order resets. In any binary search window, either the break point is in the left half (making the right half sorted) or in the right half (making the left half sorted) or not present at all (both halves sorted). You can detect which half is sorted with a single comparison: nums[lo] <= nums[mid] means the left half is sorted.

Once you know which half is sorted, you can check whether the target lies within that half's range. If it does, narrow your search to that half. If it does not, search the other half. This gives standard O(log n) binary search convergence despite the rotation.

To determine which half is sorted, compare nums[lo] to nums[mid]. If nums[lo] <= nums[mid], the left half [lo, mid] is sorted — every element from index lo to mid is in increasing order. Otherwise, nums[mid] < nums[lo], meaning the rotation break point is somewhere in the left half, which guarantees the right half [mid, hi] is sorted.

This comparison is reliable because of the uniqueness constraint. With all-unique elements, equality in nums[lo] == nums[mid] only occurs when lo == mid (a single-element window), in which case the left half is trivially sorted. This is why the condition uses <= rather than <.

You do not need to find the pivot index explicitly. The algorithm works purely by checking boundary values at each binary search step, deciding which half to commit to, and advancing the pointers accordingly.

Once you know which half is sorted, check if the target lies within that sorted range. If the left half [lo, mid] is sorted and nums[lo] <= target < nums[mid], the target must be in the left half — search left by setting hi = mid - 1. Otherwise, the target cannot be in the sorted left half, so search right by setting lo = mid + 1.

The symmetric case applies when the right half is sorted: if nums[mid] < target <= nums[hi], the target is in the right half — search right with lo = mid + 1. Otherwise, search left with hi = mid - 1.

A common mistake is checking only one condition — for example, only verifying that the half is sorted without checking the target range, or vice versa. Both conditions together are what enable correct narrowing. The target range check uses the sorted half's known boundaries to make a definitive decision.

Start with lo=0, hi=6. mid=3, nums[mid]=7. Check nums[lo]=4 <= nums[mid]=7: left half [4,5,6,7] is sorted. Is 0 in [4, 7)? No (0 < 4). So search right: lo = mid+1 = 4. Window is now indices 4-6: [0,1,2].

Now lo=4, hi=6. mid=5, nums[mid]=1. Check nums[lo]=0 <= nums[mid]=1: left half [0,1] is sorted. Is 0 in [0, 1)? Yes (0 == 0, which satisfies 0 <= 0 < 1). So search left: hi = mid-1 = 4. Window is now index 4 only: [0].

Now lo=4, hi=4. mid=4, nums[mid]=0. nums[mid] == target. Return index 4. The answer is found in 3 iterations — O(log 7) — without needing to locate the pivot first.

In Python, the solution is a single while lo <= hi loop. At each step: compute mid, check if nums[mid] == target (return mid). Then check nums[lo] <= nums[mid] to identify the sorted half. Use the target range check to decide whether to go left (hi = mid - 1) or right (lo = mid + 1). If no match found, return -1. The code is typically 15-20 lines.

In Java, the logic is identical. Use int mid = lo + (hi - lo) / 2 to avoid integer overflow. The while condition is lo <= hi. All comparisons use nums[lo], nums[mid], nums[hi], and target directly — no auxiliary arrays needed. Time complexity O(log n), space complexity O(1).

Both implementations treat the problem as standard binary search with an added sorted-half check at each iteration. The structure is: check if found, check which half is sorted, check target range, advance pointer. This four-step pattern at each iteration is the complete algorithm.

Find Minimum in Rotated Sorted Array (LeetCode 153) uses the same sorted-half identification: if nums[lo] <= nums[mid], the minimum is in the right half (or is nums[lo]); otherwise it is in the left half. The comparison logic is a subset of what LeetCode 33 requires.

Search in Rotated Sorted Array II (LeetCode 81) adds duplicates, which breaks the nums[lo] <= nums[mid] check when nums[lo] == nums[mid]. The fix is to increment lo when this occurs, degrading worst-case to O(n) but maintaining O(log n) average. Understanding LeetCode 33 makes LeetCode 81 a straightforward extension.

Binary Search Patterns more broadly — Koko Eating Bananas (LeetCode 875), Search a 2D Matrix (LeetCode 74), and Find Peak Element (LeetCode 162) — all use modified binary search with a custom condition at each step. The rotated array family is one of the best examples of adapting binary search to non-standard sorted structures.