Skip to content
ES EN
Theme: automatic

Solved exercise: recursive search in a rotated list in Python

Exam-level Python exercise on recursion and binary search in a sorted, rotated list, with hints, a tested solution and a full cost analysis.

Updated on

Exam Code Python Algorithms Exam level Tested code

Exam Code: Solved exercise: recursive search in a rotated list in Python
Programming II · Midterm ExamQuestion 2 · 2.5 points · 30 min

A server stores the timestamps of its events in a circular buffer. When the buffer is dumped into a Python list, the result is a sequence of distinct integers. The sequence was sorted in increasing order but has been rotated: an initial segment was moved to the end. For example, the increasing list [2, 5, 9, 14] rotated by two positions becomes [9, 14, 2, 5]. The rotation may be zero, in which case the list is already sorted.

Write a program that first computes the pivot, which is the index that holds the minimum value of the list. Then, for each query, it must report the index in the original list where the requested value appears, or -1 if it does not appear.

Mandatory constraints: the pivot and every search must be computed by recursive functions that run in O(log n). You may not scan the list linearly, and you may not use list.index, the in operator on the list, min, sorted or the bisect module. A linear solution scores at most 0.75 points, even if its output is correct.

Input (standard input): the first line contains n (0 ≤ n ≤ 100000). The second line contains the n integers of the list separated by spaces, and it is empty when n is 0. The third line contains q, the number of queries. It is followed by q lines with one integer each.

Output (standard output): a first line PIVOT k with the index of the minimum, or PIVOT -1 if the list is empty. Then one line per query, in the same order, with the queried value, a space and its index (or -1). Finally, a line FOUND c with the number of queries that were present in the list.

Pay attention to the edge cases: an empty list, a list with a single element, a list that is not rotated, and a list whose minimum is in the last position.

Sample input

8
14 18 23 31 2 5 9 11
6
5
31
14
11
20
2

Expected output

PIVOT 4
5 5
31 3
14 0
11 7
20 -1
2 4
FOUND 5
Recursive function that finds the pivot in logarithmic time, with a correct base case and guaranteed termination
1.0
Recursive binary search in the correct block, returning the index in the original list or -1
0.75
Input and output in the exact format, including the empty list and the one-element list
0.5
Justified time and space cost, including the depth of the call stack
0.25

Hints

Hint 1 · What does comparing the two ends of a range tell you?

Take a range v[lo..hi]. If v[lo] <= v[hi], the range does not contain the rotation. It is sorted and its minimum is v[lo]. That is your base case. If the condition fails, the drop from a large value to a small value lies inside the range.

Hint 2 · Which half contains the drop?

Look at the middle element v[mid] and compare it with v[hi], not with v[lo]. If v[mid] > v[hi], the minimum lies strictly to the right of mid. Otherwise the minimum lies in [lo, mid], and mid may itself be the minimum. Check which of the two recursive calls keeps mid.

Hint 3 · I have the pivot. What next?

With the index k of the minimum, the list splits into two sorted blocks, v[0..k-1] and v[k..n-1]. Every value in the first block is larger than every value in the second. A single range check is enough to decide which block to search. After that, an ordinary recursive binary search that uses the indices of the original list answers the query.

Solution

Explained solution

The idea is to split the problem into two independent logarithmic searches. The first one finds the pivot. The second one is a classic binary search, restricted to the sorted block where the value can possibly be. Both functions are recursive, and each call halves the range it works on.

If you want to review plain binary search and its cost analysis first, see the solved exercise on sorting and binary search with cost analysis in Python. This exercise builds on that one.

import sys


# Index of the minimum of v[lo..hi]. v is increasing and rotated, no duplicates.
def find_pivot(v, lo, hi):
    if v[lo] <= v[hi]:
        return lo
    mid = (lo + hi) // 2
    if v[mid] > v[hi]:
        return find_pivot(v, mid + 1, hi)
    return find_pivot(v, lo, mid)


# Recursive binary search in the sorted range v[lo..hi].
def binary_search(v, x, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if v[mid] == x:
        return mid
    if v[mid] < x:
        return binary_search(v, x, mid + 1, hi)
    return binary_search(v, x, lo, mid - 1)


# Decide which sorted block may contain x and search only there.
def locate(v, x, k):
    if not v:
        return -1
    if k > 0 and v[0] <= x <= v[k - 1]:
        return binary_search(v, x, 0, k - 1)
    return binary_search(v, x, k, len(v) - 1)


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    v = [int(tok) for tok in data[1:1 + n]]
    q = int(data[1 + n])
    queries = [int(tok) for tok in data[2 + n:2 + n + q]]
    k = find_pivot(v, 0, n - 1) if n > 0 else -1
    out = ['PIVOT ' + str(k)]
    found = 0
    for x in queries:
        i = locate(v, x, k)
        if i != -1:
            found += 1
        out.append(f'{x} {i}')
    out.append(f'FOUND {found}')
    print('\n'.join(out))


if __name__ == '__main__':
    main()

Reading the input. main reads all of the input with sys.stdin.read().split(). The empty line in the n = 0 case causes no trouble, because split() discards whitespace and line breaks. The n tokens after the first one form the list, the next token is q, and the remaining tokens are the queries.

The pivot. find_pivot(v, lo, hi) has a precise base case: if v[lo] <= v[hi], the range is sorted and its minimum is at lo. The values are distinct, so equality happens only when lo == hi. If the base case does not apply, the function computes mid. When v[mid] > v[hi], the drop lies between mid and hi, and the function recurses on [mid + 1, hi]. Otherwise the range [mid, hi] is sorted, so the minimum is in [lo, mid]. That call keeps mid because it may be the minimum.

Termination. In the recursive case lo < hi always holds, because v[lo] > v[hi] is impossible when lo == hi. Therefore mid < hi, and both calls work on a strictly smaller range. In the example, find_pivot starts with [0, 7]. Since 14 > 11 and v[3] = 31 > 11, it moves to [4, 7]. There v[4] = 2 <= 11, so it returns 4 after only two calls.

Choosing the block. locate relies on the fact that the whole left block v[0..k-1] is greater than the whole right block v[k..n-1]. If x lies between v[0] and v[k-1], it can only be on the left. Otherwise it can only be on the right. When k == 0 there is no left block and the whole list is searched, which is what happens in the No rotation test.

The search. binary_search is the usual recursive binary search, but with absolute indices. The index it returns is therefore already an index of the original list, and no conversion is needed. In the example, query 20 falls within the range of the left block (14 to 31) and is not there, so the program prints 20 -1 without ever looking at the right block.

Edge cases. With an empty list, find_pivot is never called, because v[0] does not exist. The program prints PIVOT -1 and locate returns -1 for every query. With one element, the base case holds on the first call. The Minimum at the end test takes the mid + 1 branch twice in a row before reaching [5, 5]. The Pivot at index 1 test exercises the branch that keeps mid. The output lines are collected in out and written with a single print.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Stepfuncxlohimid
1pivot-073
2pivot-475
3search5475
4search31031
5search31232
6search31333
7search14031
8search14000
9search11475
10search11676
11search11777
12search20031
13search20232
14search2021-
15search2475
16search2444

Test cases

CaseInputExpected outputActual outputResult
Statement example8 14 18 23 31 2 5 9 11 6 5 31 14 11 20 2PIVOT 4 5 5 31 3 14 0 11 7 20 -1 2 4 FOUND 5PIVOT 4 5 5 31 3 14 0 11 7 20 -1 2 4 FOUND 5OK
No rotation5 1 3 5 7 9 4 7 4 1 10PIVOT 0 7 3 4 -1 1 0 10 -1 FOUND 2PIVOT 0 7 3 4 -1 1 0 10 -1 FOUND 2OK
Empty list0 2 3 -1PIVOT -1 3 -1 -1 -1 FOUND 0PIVOT -1 3 -1 -1 -1 FOUND 0OK
Single element1 42 2 42 7PIVOT 0 42 0 7 -1 FOUND 1PIVOT 0 42 0 7 -1 FOUND 1OK
Minimum at the end, negatives6 -3 0 4 8 12 -10 4 -10 12 -3 5PIVOT 5 -10 5 12 4 -3 0 5 -1 FOUND 3PIVOT 5 -10 5 12 4 -3 0 5 -1 FOUND 3OK
Pivot at index 14 9 1 3 6 3 9 6 0PIVOT 1 9 0 6 3 0 -1 FOUND 2PIVOT 1 9 0 6 3 0 -1 FOUND 2OK

Actual outputs: code compiled with Python 3.13.16 and run in an isolated container on 16 November 2026.

Complexity

Time. Each call to find_pivot or binary_search does constant work and leaves a range of at most half the size. Each of the two functions therefore costs O(log n). The pivot is computed once and each query costs O(log n), so the total is O(n + q log n). The n term comes only from reading and converting the input, which cannot be avoided. The algorithmic part is O(log n + q log n).

Memory. The list takes O(n), and the queries together with the collected output take O(q). Recursion adds a stack of depth O(log n). With n = 100000 that is about 17 nested calls, far below Python's default recursion limit of 1000. You therefore do not need sys.setrecursionlimit. No function copies the list: the calls pass the indices lo and hi, not sublists.

If each call passed a slice such as v[mid + 1:], every level would copy half the list, and the cost would grow to O(n) per search. The returned index would also be relative to the slice and would need correcting.

Common mistakes

  • Recursing on [lo, mid - 1] when v[mid] <= v[hi]. This discards the minimum itself, and the test with the pivot at index 1 catches it.
  • Comparing v[mid] with v[lo] instead of v[hi] without handling the unrotated list separately. On a sorted list this picks the wrong half.
  • Passing sublists such as v[:mid] to the recursive calls. This breaks the logarithmic cost and returns indices relative to the sublist rather than to the original list.
  • Calling find_pivot(v, 0, -1) on an empty list. v[0] raises IndexError and the program prints nothing.
  • Forgetting the k == 0 case in locate. In the condition v[0] <= x <= v[k - 1], v[-1] is then the last element, so the program searches an empty or wrong range.
  • Reading line by line with input().split() and assuming the second line always holds numbers. When n = 0, the empty line shifts the reading unless it is handled explicitly.

Variants

Turn the recursive functions into iterative ones

Both functions are tail-recursive: the recursive call is the last action, and its result is returned unchanged. They therefore convert mechanically into a while loop that updates lo and hi. In find_pivot, the loop condition is the negation of the base case. The time cost stays the same, and the extra memory drops from O(log n) to O(1). Python does not eliminate tail calls, so this version is the one to prefer in production code.

import sys


def find_pivot(v):
    lo, hi = 0, len(v) - 1
    while v[lo] > v[hi]:
        mid = (lo + hi) // 2
        if v[mid] > v[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo


def binary_search(v, x, lo, hi):
    while lo <= hi:
        mid = (lo + hi) // 2
        if v[mid] == x:
            return mid
        if v[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def locate(v, x, k):
    if not v:
        return -1
    if k > 0 and v[0] <= x <= v[k - 1]:
        return binary_search(v, x, 0, k - 1)
    return binary_search(v, x, k, len(v) - 1)


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    v = [int(tok) for tok in data[1:1 + n]]
    q = int(data[1 + n])
    queries = [int(tok) for tok in data[2 + n:2 + n + q]]
    k = find_pivot(v) if n > 0 else -1
    out = ['PIVOT ' + str(k)]
    found = 0
    for x in queries:
        i = locate(v, x, k)
        if i != -1:
            found += 1
        out.append(f'{x} {i}')
    out.append(f'FOUND {found}')
    print('\n'.join(out))


if __name__ == '__main__':
    main()

A single recursive search without computing the pivot

You can also search directly. In every call, at least one of the halves [lo, mid] or [mid, hi] is sorted, and comparing v[lo] with v[mid] tells you which one. If x falls within the range of the sorted half, recurse into it. Otherwise recurse into the other half. This is more compact, but it has more branches where a < can be confused with a <=. The statement also asks you to print the pivot, so you would have to compute it anyway.

On the syllabus

Searching is a core topic in algorithms courses on both coasts of the US. The syllabus of MIT 6.006 Introduction to Algorithms lists sorting, searching data structures and algorithmic paradigms among its contents. The course page of Stanford CS161 Design and Analysis of Algorithms mentions its focus on algorithms for sorting and searching. Carnegie Mellon 15-210 stresses defining a problem cleanly and analysing its cost in terms of work, which is what the complexity section of this exercise asks for.

Outside the US, recursion has its own unit in the syllabus of Estructuras de Datos at UNAM's Facultad de Ciencias, just before lists and binary search trees.

Article generated with AI.larebelion

Byline

· Chief editor · English edition · London

“A logarithmic search that breaks on one element is not fast. It is a bug that shows up quickly.”

Comments (0)

No comments yet. You can be the first.

Write a comment