---
title: "Search in a rotated sorted array: why one half is always sorted"
url: https://algopath.pro/blog/search-in-rotated-sorted-array
language: en
summary: "How binary search survives a rotation. The one comparison that finds the sorted half, Python code for the target and the minimum, a traced run, duplicates and the mistakes."
updated: 2026-10-25
---

# Search in a rotated sorted array: why one half is always sorted

**Short answer.** Binary search still works on a rotated sorted array. One half is always sorted. At each step, find the sorted half. Check whether the target lies inside it. Time O(log n). It is the pattern behind two classic LeetCode problems. Below: the idea, Python code, a traced run and the mistakes.

 

## What is a rotated sorted array?

 

Take a sorted array [1, 2, 3, 4, 5, 6, 7]. Shift it around by three positions. You get [4, 5, 6, 7, 1, 2, 3]. That is a rotated sorted array.

 

It is two sorted pieces. The drop from a large value to a small one is the pivot point. Here it is the step from 7 to 1.

 

Plain binary search breaks on it. The middle value does not tell you which way to go.

 

## How does binary search pick a half in a rotated sorted array?

 

Take the middle index mid. Compare nums[lo] with nums[mid]. If nums[lo] is not above nums[mid], the left half is sorted. Otherwise the right half is.

 

Now look at the target. If it falls inside the sorted half by value, go there. Otherwise go to the other half.

 

Each step halves the range. Hence O(log n).

 

## What does one run look like?

 

Array [4, 5, 6, 7, 0, 1, 2], target 0. lo = 0, hi = 6, mid = 3, nums[mid] = 7. nums[lo] = 4 is not above 7. The left half is sorted: 4 to 7. Target 0 is not in it, go right: lo = 4.

 

mid = 5, nums[mid] = 1. nums[lo] = 0 is not above 1, left half [0, 1] is sorted. Target 0 is in it, hi = 4. mid = 4, nums[mid] = 0. Found, answer 4.

 

## How do you write it in Python?

 

```
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:            # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:             # minimum is right of mid
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]
```

 

The second function compares mid with the right end. If nums[mid] is above nums[hi], the pivot is to the right. Otherwise it is to the left or at mid.

 

## How do the rotated sorted array problems differ?

 

| Problem | Compare mid with | Duplicates | Time |
| --- | --- | --- | --- |
| Search in Rotated Sorted Array | nums[lo] and the target | No | O(log n) |
| Search in Rotated Sorted Array II | Same, plus a shrink on ties | Yes | O(log n), worst O(n) |
| Find Minimum in Rotated Sorted Array | nums[hi] | No | O(log n) |
| Find the rotation count | Index of the minimum | No | O(log n) |

 

## What changes when there are duplicates?

 

Suppose nums[lo], nums[mid] and nums[hi] are all equal. Neither half is provably sorted. Example: [1, 1, 1, 0, 1].

 

The fix: move lo one step right and hi one step left. Then continue. Worst case O(n), but ordinary inputs stay logarithmic.

 

## When does a problem need this pattern?

 

- "A sorted array rotated at an unknown pivot."
- "Find the target in O(log n)" in such an array.
- "Find the minimum" or "how many times was it rotated".
- "The array rises, then falls": the neighbouring peak problem.

 

## How do you find the minimum in a rotated sorted array?

 

Use find_min above. Compare the middle with the right end. If the middle is bigger, the minimum is to the right. Drop the left half and the middle. Otherwise drop the right half.

 

Example [4, 5, 6, 7, 0, 1, 2]. mid = 3, value 7, above 2, so lo = 4. mid = 5, value 1, not above 2, so hi = 5. mid = 4, value 0, hi = 4. Answer 0.

 

## What mistakes break the search?

 

- Comparing nums[lo] and nums[mid] with strict less-than. A one-element half then counts as unsorted.
- Non-strict bounds on both sides of the target check. The loop never ends.
- Comparing with nums[lo] instead of nums[hi] in find_min. An unrotated array breaks it.
- Finding the pivot with a linear scan. That throws away the whole point.

 

## How do you explain it in an interview?

 

Say: one half is always sorted. Show the single comparison that finds it. Then say how you decide where the target is.

 

Give O(log n): every step discards half. Mention duplicates as a separate case, even unasked.

 

Drill this pattern on the [binary search on a rotated array](/patterns/binary-search-rotated) page. The base skill lives on the [binary search](/patterns/binary-search-array) page.

 

## FAQ

 

### Can you find the pivot first and then search normally?

 

Yes. That is two binary searches instead of one, still O(log n). The one-pass version is shorter. The two-step version is easier to explain.

 

### How do you find how many positions it was rotated by?

 

That is the index of the minimum. Return lo from find_min instead of nums[lo]. In the array above the minimum sits at index 4. The rotation is 4.

 

### What if the array is not rotated at all?

 

The code handles it. The left half is always sorted. The search reduces to the plain one.

 

### How do you find a peak in an array that rises then falls?

 

Compare nums[mid] with nums[mid + 1]. If the right one is bigger, the peak is right. Otherwise left or at mid. Same idea, different comparison.