How do you search in a rotated sorted array?

Q: How do you search in a rotated sorted array?

# Searching a Rotated Sorted Array (Python) **Target Audience:** Learners who know basic binary search and are preparing for coding interviews. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory. ## 1. Why This Even Matters — A Story First A librarian keeps a shelf of books sorted by number: 1, 2, 3, ... 100. One night someone takes the first 40 books and puts them, still in order, at the end of the shelf. Now the shelf reads 41, 42, ..., 100, 1, 2, ..., 40. It is no longer sorted, so ordinary binary search breaks — and yet it is *almost* sorted: it is two sorted runs glued together. Can you still find book 17 by looking at only a handful of books? Yes. Open the shelf in the middle.

The problem

Question presented to candidate: "You are given a sorted array of distinct integers that has been rotated at an unknown point, like [4, 5, 6, 7, 0, 1, 2], and a target. Return its index or -1, in O(log n) time. Please code it in Python."

What a strong answer should cover:

The key insight: at any midpoint at least one half is sorted, and nums[lo] <= nums[mid] tells you which.
Correct range checks: search the sorted half only if the target lies within its end values, otherwise the other half.
O(log n) time and O(1) space, plus the two-pass alternative (find the rotation point, then binary search one run).
Edge cases: not rotated, one or two elements (the <=), empty array, target absent.
The duplicates follow-up: shrink both ends when nums[lo] == nums[mid] == nums[hi]; worst case O(n).
Python specifics: chained comparisons (nums[lo] <= target < nums[mid]) for the range test, // for the midpoint, and why nums.index is the O(n) brute force.

Clarifying questions expected:

Are all values distinct?
Should I return the index or just whether it exists?
Can the array be empty or not rotated at all?

Code / implementation expected: Yes — a one-pass O(log n) Python solution, tested on edge cases.

binary-search
arrays

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Searching a Rotated Sorted Array (Python)

Target Audience: Learners who know basic binary search and are preparing for coding interviews. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory.

1. Why This Even Matters — A Story First

A librarian keeps a shelf of books sorted by number: 1, 2, 3, ... 100. One night someone takes the first 40 books and puts them, still in order, at the end of the shelf. Now the shelf reads 41, 42, ..., 100, 1, 2, ..., 40. It is no longer sorted, so ordinary binary search breaks — and yet it is almost sorted: it is two sorted runs glued together.

The solution is hidden so you can try first

7 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonOne-pass search, checked against every rotation

Practice

PythonRotation point, two-pass search, and duplicates

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.