Searching in Rotated Sorted Arrays

A rotated sorted array is a sorted array that has been cut at some unknown pivot and the two pieces swapped, like [0,1,2,4,5,6,7] becoming [4,5,6,7,0,1,2]. It shows up constantly in interviews because it looks like a job for linear search, but it can still be searched in O(log n) if you adapt binary search to reason about which half of the array is sorted at each step. This lesson builds that modified binary search from scratch, extends it to arrays with duplicates, and shows how to find the rotation point itself.

Overview / How it works

Picture the array [4,5,6,7,0,1,2]. It is not sorted end to end, but it is made of exactly two sorted runs: [4,5,6,7] and [0,1,2]. The key insight is this: whenever you split the array in half at any point, at least one of the two halves is guaranteed to be normally sorted, even if the other half contains the rotation break. That’s because the rotation break can only exist in one of the two halves—it cannot be in both.

So the algorithm looks like ordinary binary search, but with an extra decision at every step:

1. Compute mid. If nums[mid] is the target, you’re done.
2. Figure out which half, [left, mid] or [mid, right], is normally sorted. You can tell by comparing nums[left] to nums[mid]: if nums[left] <= nums[mid], the left half is sorted; otherwise the right half must be sorted.
3. Check whether the target falls inside the value range of the sorted half. If it does, recurse (or narrow the window) into that half, because a normal binary-search comparison is valid there. If it doesn’t, the target must be in the other half, so narrow into that one instead—even though it might still contain the rotation.
4. Repeat until the window is empty or you find the target.

Every iteration still eliminates roughly half of the remaining elements, exactly like standard binary search, which is why the algorithm keeps its O(log n) time complexity even though the array as a whole isn’t sorted.

A related problem: finding the rotation point

A close cousin of this problem is finding the index of the minimum element, i.e. the rotation point. The same idea applies: compare nums[mid] to nums[right]. If nums[mid] > nums[right], the minimum must be to the right of mid (the rotation break is in the right half). Otherwise the minimum is at mid or to its left. This is useful on its own and also explains why the rotation exists in the first place: the array is really two sorted arrays glued together at the minimum.

Time and Space Complexity

Let n be the number of elements in the array.

Operation	Best case	Average case	Worst case	Space
Search, no duplicates	O(1)	O(log n)	O(log n)	O(1)
Find rotation point (minimum)	O(1)	O(log n)	O(log n)	O(1)
Search with duplicates allowed	O(1)	O(log n)	O(n)	O(1)

The best case is when the target sits at the very first mid we check—O(1). The average and worst case without duplicates stay at O(log n) because, as argued above, every comparison still discards half of the remaining search space; the only difference from classic binary search is that we spend a constant amount of extra work per iteration deciding which half is sorted, and constants don’t change the asymptotic class.

When duplicates are allowed, comparing nums[left], nums[mid], and nums[right] can become ambiguous—if all three are equal, you cannot tell which side is sorted or where the rotation is. The only safe move is to shrink the window by one from each side (left += 1, right -= 1) and try again. In the worst case (e.g. an array like [1,1,1,1,1,1,0,1]) this degrades to checking almost every element, giving O(n) worst-case time. Space complexity is O(1) throughout because the iterative version only tracks a few integer pointers—no extra data structures or recursion stack are needed.

Examples

Example 1: Search without duplicates

def search_rotated(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1


nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0))
print(search_rotated(nums, 3))

Output:

4
-1

Searching for 0: at mid=3 (nums[3]=7), the left half [4,5,6,7] is sorted, but 0 isn't in the range [4,7), so we move right. The window shrinks to [0,1,2] at indices 4–6, and two more steps land exactly on index 4. Searching for 3, which doesn't exist in the array at all, the pointers keep narrowing the window until left passes right, and the function correctly returns -1.

Example 2: Finding the rotation point

def find_minimum(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]


nums = [4, 5, 6, 7, 0, 1, 2]
print(find_minimum(nums))

nums2 = [1, 2, 3, 4, 5]
print(find_minimum(nums2))

Output:

0
1

For the rotated array, the loop keeps discarding the half that cannot contain the minimum, because if nums[mid] > nums[right] the break is strictly to the right of mid. It converges on index 4, value 0. The second call passes an array that was never rotated at all—a common edge case—and the algorithm still works correctly, converging on index 0, the true minimum, because nums[mid] is never greater than nums[right] in a fully sorted array.

Example 3: Search with duplicates allowed

def search_with_duplicates(nums: list[int], target: int) -> bool:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return True
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
        elif nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return False


nums = [1, 0, 1, 1, 1]
print(search_with_duplicates(nums, 0))
print(search_with_duplicates(nums, 2))

Output:

True
False

At the first step, nums[left], nums[mid], and nums[right] are all 1, so we can't tell which side is sorted—we shrink both pointers inward instead of guessing. That resolves the ambiguity, and the next comparison correctly identifies the left half as sorted, narrowing straight to index 1 where the target 0 lives. Searching for 2, which isn't in the array, the same shrinking happens again near the end, and the pointers eventually cross, correctly returning False.

How it works step by step

Trace search_rotated([4, 5, 6, 7, 0, 1, 2], 0) in detail:

• Step 1: left=0, right=6. mid=3, nums[3]=7. Not the target. nums[0]=4 <= nums[3]=7, so the left half [0,3] is sorted. Is 4 <= 0 < 7? No. So the target must be in the right half: left = mid + 1 = 4.
• Step 2: left=4, right=6. mid=5, nums[5]=1. Not the target. nums[4]=0 <= nums[5]=1, so the left half [4,5] is sorted. Is 0 <= 0 < 1? Yes. Narrow into that half: right = mid - 1 = 4.
• Step 3: left=4, right=4. mid=4, nums[4]=0. Match—return 4.

Notice how the window shrinks from 7 elements, to 2, to 1—each step still roughly halves the search space, which is the same logarithmic shrinkage as ordinary binary search. The only extra work per step is the constant-time check of which half is sorted.

Common Mistakes

Mistake 1: Treating it like a normal sorted array

The most common bug is writing plain binary search and forgetting the array isn't fully sorted, so the classic "go left if nums[mid] > target, go right otherwise" rule silently gives wrong answers:

def broken_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


nums = [4, 5, 6, 7, 0, 1, 2]
print(broken_search(nums, 0))

Output:

-1

The target 0 is sitting right there at index 4, but this returns -1. At mid=3, nums[3]=7, and since 7 is not less than 0, the code assumes the target must be to the left—the assumption that's true for a normally sorted array, but false here because the rotation break hides the target in the right half. The fix is the sorted-half check from Example 1: always determine which side is actually sorted before deciding where to look.

Mistake 2: An off-by-one in the sorted-half check

Using a strict < instead of <= when comparing nums[left] and nums[mid] breaks on small windows where left == mid:

def broken_half_check(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] < nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1


def fixed_half_check(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1


nums = [3, 1]
print(broken_half_check(nums, 1))
print(fixed_half_check(nums, 1))

Output:

-1
1

On a 2-element window [3, 1], left and mid are the same index, so nums[left] < nums[mid] is 3 < 3, which is False—the broken version wrongly falls into the "right half is sorted" branch and eliminates the half that actually contains the target. Using <= correctly treats a single-element or equal-valued left half as sorted, since a run of length one is trivially sorted.

Best Practices

• Only reach for the modified binary search when you specifically know the array was sorted and then rotated at an unknown pivot; for an arbitrary unsorted array, this technique doesn't apply and you need a different approach.
• Always determine the sorted half using nums[left] <= nums[mid] (with <=, not <) so single-element or already-equal windows are handled correctly.
• If the problem says duplicates are possible, use the three-way equality check (nums[left] == nums[mid] == nums[right]) to shrink the window when the sorted half is ambiguous, and mention in an interview that this degrades the worst case to O(n).
• Keep the rotation-point search (find_minimum) as a separate, reusable function rather than folding it into the search—many problems (like "how many times was the array rotated") only need the minimum, not a target search.
• Test on edge cases every time: an empty array, a single-element array, an array with no rotation at all, and a target equal to the first or last element.
• Prefer the iterative form shown here over recursion; it avoids any recursion-depth concerns and keeps space complexity at O(1).

Practice Exercises

• Exercise 1: Given a rotated sorted array with no duplicates, such as [6,7,0,1,2,4,5], write a function that returns the index of target=4, or -1 if it isn't present. Expected output for this input: 5.
• Exercise 2: Given [11,13,15,17,2,4,7], find the number of times the array was rotated (hint: this equals the index of the minimum element, found with find_minimum). Expected output: 4.
• Exercise 3: Given a rotated sorted array that may contain duplicates, such as [2,2,2,3,4,2], determine whether target=3 exists. Trace through why the ambiguous-half case triggers here, and state the worst-case time complexity of your solution.

Summary

• A rotated sorted array is two sorted runs joined at an unknown pivot; splitting it anywhere always leaves at least one half normally sorted.
• The modified binary search checks which half is sorted, then checks whether the target's value falls inside that half's range, narrowing the window by half each iteration—giving O(log n) time and O(1) space.
• Finding the rotation point (minimum element) uses the same halving idea by comparing nums[mid] to nums[right], also in O(log n) time.
• Duplicates can make nums[left], nums[mid], and nums[right] all equal, making it impossible to tell which half is sorted; shrinking both pointers by one resolves the ambiguity but degrades worst-case time to O(n).
• The most common bugs are forgetting the array isn't fully sorted (using plain binary search logic) and using a strict < instead of <= when identifying the sorted half, which breaks on small windows.