Find a value in a rotated sorted list

Searching sorted data Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

vals, target = [6, 7, 9, 1, 3, 4], 3
lo, hi = 0, len(vals) - 1
seen = []
while lo <= hi:
    mid = (lo + hi) // 2
    seen.append(vals[mid])
    if vals[mid] == target:
        break
    if vals[lo] <= vals[mid]:
        if vals[lo] <= target < vals[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    elif vals[mid] < target <= vals[hi]:
        lo = mid + 1
    else:
        hi = mid - 1
print(seen)

Options[9, 3][9, 1, 3][1, 3]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [9, 3]

Right: the left half [6, 7, 9] is sorted and 3 is not in it, so the search jumps right and finds 3.

Checking which half is sorted lets the search discard half the list even across the rotation.

Why not the others?

B [9, 1, 3]. After 9 the range is [1, 3, 4], whose middle is 3.
C [1, 3]. The first middle index is 2, which holds 9.

30-second answer

At each step at least one half around mid is sorted. If the left half is sorted (vals[lo] <= vals[mid]) and the target lies inside it, search there; otherwise search the right. Mirror the logic when the right half is sorted. O(log n) time and O(1) space.

Practise saying it · 60 s. No recording, just a timer

Explain searching a rotated sorted list.

Say your answer out loud, then check which of these points you covered:

One half is sorted
Check if the target is in it
O(log n)

Deep dive

Each step still discards half the list; you just decide which half differently.

Finding the rotation point first, then running a normal search on the right piece, also works in O(log n).

Use <= when testing the left half so a two-item range is handled.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def find_rotated(vals: list[int], target: int) -> int:
    lo, hi = 0, len(vals) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if vals[mid] == target:
            return mid
        if vals[lo] <= vals[mid]:  # left part is in order
            if vals[lo] <= target < vals[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        elif vals[mid] < target <= vals[hi]:  # right part is in order
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Common mistakes

Testing the target against only one end of the sorted half.
Getting the <= wrong when lo == mid.

Senior take & follow-ups

Say 'one half is always sorted' first; then each branch is easy to justify.

Follow-up questions

Think of your answer first, then open the hint.

How does this change with duplicates?
Show hint
If vals[lo] == vals[mid] == vals[hi] you cannot tell which half is sorted; shrink both ends, O(n) worst case.
Can you do it with one pass of lower bound?
Show hint
Yes, by mapping values to a key that accounts for which side of the rotation they lie on.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.