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

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
2Expected 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.
Step-by-step trace · generated by running the code
| Step | func | x | lo | hi | mid |
|---|---|---|---|---|---|
| 1 | pivot | - | 0 | 7 | 3 |
| 2 | pivot | - | 4 | 7 | 5 |
| 3 | search | 5 | 4 | 7 | 5 |
| 4 | search | 31 | 0 | 3 | 1 |
| 5 | search | 31 | 2 | 3 | 2 |
| 6 | search | 31 | 3 | 3 | 3 |
| 7 | search | 14 | 0 | 3 | 1 |
| 8 | search | 14 | 0 | 0 | 0 |
| 9 | search | 11 | 4 | 7 | 5 |
| 10 | search | 11 | 6 | 7 | 6 |
| 11 | search | 11 | 7 | 7 | 7 |
| 12 | search | 20 | 0 | 3 | 1 |
| 13 | search | 20 | 2 | 3 | 2 |
| 14 | search | 20 | 2 | 1 | - |
| 15 | search | 2 | 4 | 7 | 5 |
| 16 | search | 2 | 4 | 4 | 4 |
Test cases
| Case | Input | Expected output | Actual output | Result |
|---|---|---|---|---|
| Statement example | 8
14 18 23 31 2 5 9 11
6
5
31
14
11
20
2 | PIVOT 4
5 5
31 3
14 0
11 7
20 -1
2 4
FOUND 5 | PIVOT 4
5 5
31 3
14 0
11 7
20 -1
2 4
FOUND 5 | OK |
| No rotation | 5
1 3 5 7 9
4
7
4
1
10 | PIVOT 0
7 3
4 -1
1 0
10 -1
FOUND 2 | PIVOT 0
7 3
4 -1
1 0
10 -1
FOUND 2 | OK |
| Empty list | 0
2
3
-1 | PIVOT -1
3 -1
-1 -1
FOUND 0 | PIVOT -1
3 -1
-1 -1
FOUND 0 | OK |
| Single element | 1
42
2
42
7 | PIVOT 0
42 0
7 -1
FOUND 1 | PIVOT 0
42 0
7 -1
FOUND 1 | OK |
| Minimum at the end, negatives | 6
-3 0 4 8 12 -10
4
-10
12
-3
5 | PIVOT 5
-10 5
12 4
-3 0
5 -1
FOUND 3 | PIVOT 5
-10 5
12 4
-3 0
5 -1
FOUND 3 | OK |
| Pivot at index 1 | 4
9 1 3 6
3
9
6
0 | PIVOT 1
9 0
6 3
0 -1
FOUND 2 | PIVOT 1
9 0
6 3
0 -1
FOUND 2 | OK |
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]whenv[mid] <= v[hi]. This discards the minimum itself, and the test with the pivot at index 1 catches it. - Comparing
v[mid]withv[lo]instead ofv[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]raisesIndexErrorand the program prints nothing. - Forgetting the
k == 0case inlocate. In the conditionv[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



Comments (0)
No comments yet. You can be the first.
Write a comment