Search in Rotated Sorted Array: Modified Binary Search

Search in Rotated Sorted Array is LeetCode 33, and it is one of those problems that separates people who memorized binary search from people who actually understand it. A regular binary search works on a sorted array. This array was sorted, then someone rotated it. Your job is to still find the target in O(log n).

The trick is that even in a rotated array, you always have enough information to decide which half to search. Once you see that, the problem clicks.

The problem

You are given an integer array nums that was sorted in ascending order, then rotated at some unknown pivot. All values are unique. Given a target, return its index or -1 if it is not in the array. You must solve it in O(log n) time.

Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0. The answer is 4 because nums[4] = 0.

The original sorted array was [0, 1, 2, 4, 5, 6, 7]. It got rotated so that 4 ended up at the front. Now there is a "break" in the middle where 7 drops to 0. That break is the pivot point.

Why regular binary search does not work directly

In a standard sorted array, you check the midpoint and know immediately which half the target is in. Target bigger than mid? Go right. Target smaller? Go left.

In a rotated array, the midpoint alone does not tell you enough. Look at nums = [4, 5, 6, 7, 0, 1, 2] with target = 0. The midpoint is index 3 with value 7. The target 0 is less than 7, but it is in the right half, not the left. The usual "smaller means go left" logic breaks down.

So you need a different way to decide. And there is a clean one.

The key insight: one half is always sorted

Here is the observation that makes this problem solvable in O(log n). No matter where you pick mid in a rotated sorted array, at least one of the two halves (left half [lo..mid] or right half [mid..hi]) is guaranteed to be in proper sorted order.

Why? The rotation creates exactly one "break point" in the array. That break can only be in one half. The other half has no break, so it is perfectly sorted.

This is the entire key to the modified binary search. At each step:

1. Figure out which half is sorted (compare nums[lo] with nums[mid])
2. Check if the target falls within the sorted half's range
3. If yes, search that half. If no, search the other half.

You never need to find the pivot explicitly. You just need to know which half is safe to reason about.

Visual walkthrough

Let's search for target = 0 in [4, 5, 6, 7, 0, 1, 2]. At each step we identify the sorted half (highlighted in green) and decide where to search next.

Three comparisons. Out of 7 elements, we found our target in O(log n) time. The modified binary search works just like regular binary search, but with an extra check at each step to figure out which half is sorted.

The code

Here is the complete Python solution for LeetCode 33, search in rotated sorted array:

def search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return mid

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

    return -1

Let's break this down piece by piece.

The setup is identical to standard binary search: lo and hi define an inclusive search range, and we compute mid the same way.

if nums[lo] <= nums[mid] tells us the left half [lo..mid] is sorted. There is no rotation break in it. We use <= instead of < because when lo == mid (two elements left), the "left half" is just one element and it is trivially sorted.

if nums[lo] <= target < nums[mid] checks whether the target sits inside the sorted left half. If it does, we can safely narrow to the left (hi = mid - 1). If it does not, the target must be in the right half (lo = mid + 1).

The else branch handles the case where the right half [mid..hi] is sorted. Same logic, flipped: check if the target is in the sorted right half's range, and go there if so.

Why nums[lo] <= nums[mid] works as the sorted-half check

This is the part that confuses people, so let's think about it carefully.

If nums[lo] <= nums[mid], every element from index lo to mid is in ascending order. The rotation break is not in this half. Why? Because if the break were between lo and mid, there would be a drop, and nums[lo] would be larger than some element before mid, which contradicts sorting up to mid.

If nums[lo] > nums[mid], then the break IS somewhere in the left half, which means the right half [mid..hi] must be cleanly sorted.

There is no third case. The break is either in the left half or the right half (or the array is not rotated at all, in which case the left half check succeeds and everything works normally).

Complexity analysis

Time: O(log n). Each iteration eliminates half the search space, just like regular binary search. The extra comparison to determine which half is sorted is O(1).

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

This is optimal. You cannot do better than O(log n) for searching in a rotated sorted array, and you cannot use less than O(1) space.

Edge cases to watch for

• No rotation: nums = [1, 2, 3, 4, 5]. The algorithm works fine because the left half is always sorted, and we never hit the else branch.
• Single element: nums = [1]. lo == hi == mid, we check if nums[mid] == target and either return 0 or -1.
• Two elements: nums = [2, 1], target = 1. lo=0, hi=1, mid=0. nums[0]=2 <= nums[0]=2, so left is "sorted." target=1 is not in [2, 2), so we go right: lo=1. Now lo==hi==mid=1, nums[1]=1==target. Found it.
• Target not in array: the loop exits when lo > hi and we return -1. Same as standard binary search.
• Rotation at index 0 or n-1: these are edge rotations where the array is either not rotated at all or only the last element wrapped around. Both cases are handled by the sorted-half check.

The building blocks

This problem is built on one core building block: search space halving (binary-search-on-answer).

The underlying mechanism is the same binary search skeleton you already know: maintain [lo, hi], compute mid, eliminate half the range. What changes is the decision logic. In standard binary search, you compare nums[mid] to the target. Here, you first figure out which half is sorted, then check if the target is in that sorted range.

# Standard binary search decision:
if nums[mid] < target:
    lo = mid + 1
else:
    hi = mid - 1

# Rotated array decision:
if left_half_is_sorted:
    if target_in_left_range:
        hi = mid - 1
    else:
        lo = mid + 1
else:
    if target_in_right_range:
        lo = mid + 1
    else:
        hi = mid - 1

The skeleton is identical. The only new piece is the "which half is sorted?" check. Once you can write the basic binary search template from memory, this problem is just plugging in a slightly more complex comparison.

This same "modified binary search" pattern shows up whenever you need to search in a structure that is almost sorted:

• Find Minimum in Rotated Sorted Array: binary search to find the pivot itself
• Search in Rotated Sorted Array II (with duplicates): same idea but worst case degrades to O(n)
• Find Peak Element: the "sorted" structure is local monotonicity, not global sorting

From understanding to recall

Right now, the logic makes sense. You check which half is sorted, you check if the target is in the sorted range, you go left or right. Clear enough.

But in an interview, under pressure, things get fuzzy. Was it nums[lo] <= nums[mid] or nums[lo] < nums[mid]? Do you check the target against nums[lo] and nums[mid], or nums[mid] and nums[hi]? The boundary conditions are easy to mix up when your brain is working on five things at once.

Spaced repetition fixes this. You type the solution from scratch today, then tomorrow, then in three days. Each time you rebuild the sorted-half check and the target-range comparison from memory. After a few rounds, you do not need to think about whether it is <= or <. Your fingers just type it.

The modified binary search pattern is one of the most commonly tested medium-difficulty patterns. Getting it into long-term muscle memory pays off far more than re-deriving it each time.

Related posts

• Binary Search (LeetCode 704): The Foundation - Master the standard binary search template first, then this rotated variant becomes a small modification on top
• Binary Search: More Than Finding a Number - The full guide to binary search patterns including search on the answer space and left-bound/right-bound variants

---

Visual Learner? Master the fundamentals first with our Binary Search Explained visual guide.