Search in Rotated Sorted Array: LeetCode 33 Walkthrough

Search in Rotated Sorted Array (#33) is the most frequently tested binary search Medium on LeetCode. It combines two concepts that interviewers love — rotation detection and target searching — into a single O(log n) algorithm. If you can solve this problem cleanly, you have demonstrated that you truly understand binary search beyond the textbook version.

The setup is deceptively simple: you are given a sorted array that has been rotated at some unknown pivot, and you need to find a target value. Return its index if it exists, or -1 if it does not. The catch is that a brute-force linear scan is not acceptable — you must achieve O(log n) time complexity, which means binary search is the only option.

This problem appears constantly at Google, Amazon, Meta, and Bloomberg. It is a natural follow-up to Find Minimum in Rotated Sorted Array (#153), and mastering it gives you the confidence to handle any binary search variant that shows up in an interview.

You are given an integer array nums that was originally sorted in ascending order and then rotated between 1 and n times. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] after rotating at index 3. You are also given a target integer, and you need to return the index of the target in nums, or -1 if it is not present.

The constraint that makes this interesting is the O(log n) requirement. A simple linear scan would work in O(n), but the problem explicitly demands logarithmic time. This tells you immediately that binary search is required — but standard binary search assumes the array is fully sorted, which it is not after rotation.

The rotation creates two sorted subarrays. In [4,5,6,7,0,1,2], the left portion [4,5,6,7] is sorted and the right portion [0,1,2] is sorted. The challenge is modifying binary search to work correctly when the array is split into two sorted halves instead of one.

The breakthrough for this problem is a single observation: no matter where you place your mid pointer, at least one half of the array is guaranteed to be sorted. This is true because the rotation only breaks the sort at one point — the pivot. So when you split the array at mid, the pivot can only be in one half, leaving the other half perfectly sorted.

Here is how you use this. Compare nums[left] with nums[mid]. If nums[left] is less than or equal to nums[mid], the left half [left, mid] is sorted. Otherwise, the right half [mid, right] is sorted. Once you know which half is sorted, you can check whether the target falls within that sorted range using a simple bounds check.

If the target is within the sorted half, you narrow your search to that half — exactly like standard binary search. If the target is not in the sorted half, you search the other half instead. Either way, you eliminate half the array at every step, giving you the O(log n) guarantee that the problem demands.

The implementation follows a modified binary search. Initialize left at 0 and right at nums.length - 1. While left is less than or equal to right, compute mid as usual. If nums[mid] equals the target, return mid immediately.

Next, determine which half is sorted. If nums[left] is less than or equal to nums[mid], the left half is sorted. In that case, check whether the target falls in the range [nums[left], nums[mid]). If it does, move right to mid - 1. If it does not, move left to mid + 1. This is the search rotated array logic in action.

If the left half is not sorted, then the right half must be sorted. Check whether the target falls in the range (nums[mid], nums[right]]. If it does, move left to mid + 1. If it does not, move right to mid - 1. After the loop, if you have not returned, the target is not present — return -1.

Let us trace through [4,5,6,7,0,1,2] with target = 0. Initially left = 0, right = 6, so mid = 3 and nums[mid] = 7. Since nums[left] = 4 is less than or equal to nums[mid] = 7, the left half [4,5,6,7] is sorted. Is target 0 in the range [4, 7]? No — 0 is less than 4. So we search right: left = mid + 1 = 4.

Now left = 4, right = 6, so mid = 5 and nums[mid] = 1. Check: nums[left] = 0 is less than or equal to nums[mid] = 1, so the left half [0, 1] is sorted. Is target 0 in the range [0, 1]? Yes — 0 is greater than or equal to 0 and less than 1. So we search left: right = mid - 1 = 4.

Now left = 4, right = 4, so mid = 4 and nums[mid] = 0. That equals our target, so we return index 4. The algorithm found the answer in just three iterations — true O(log n) performance on a rotated array. This is the rotated sorted binary search in action.

The first edge case is an array that is not actually rotated — it is already fully sorted. For example, [1,2,3,4,5] with no rotation. The algorithm handles this naturally because nums[left] will always be less than or equal to nums[mid], and the left-half logic works exactly like standard binary search.

The second edge case is when the target sits exactly at the pivot point — the smallest element in the array. This works because the algorithm will eventually narrow down to a window containing the pivot. A single-element array is another case: left equals right equals mid, and you either match the target or return -1.

The final edge case is when the target does not exist in the array at all. The algorithm handles this by exhausting the search space — left will eventually exceed right, and you return -1. No special handling is needed, which is a sign that the algorithm is well-designed.

Search in Rotated Sorted Array (#33) teaches you that binary search is not just for perfectly sorted arrays — it works anytime you can reliably eliminate half the search space. The key is identifying an invariant (one half is always sorted) and using it to make a decision at every step. This thinking transfers to dozens of other binary search variants.

This problem builds directly on Find Minimum in Rotated Sorted Array (#153). In problem 153 you find the pivot; in problem 33 you search for a specific target. Together they form the rotated array binary search family, which is one of the most common FAANG interview patterns. If you can solve both, you can handle any rotation-based binary search question.

Review this problem regularly with YeetCode flashcards so the sorted-half check becomes automatic. In an interview you do not want to waste time deciding whether to compare nums[left] with nums[mid] or nums[mid] with nums[right] — that logic should be instant. Spaced repetition turns the pattern into muscle memory, letting you focus on communicating your approach instead of debugging your bounds.