These are the notes for Python Coding Questions, episode 22: searching and sorting questions. Three interview favourites: find a value in a million sorted items, including its first and last position; write merge sort and measure why it beats the simple sorts; and sort a rank list by two keys without the second sort undoing the first.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings change a little from run to run and from computer to computer; the pattern (seconds vs milliseconds, ×4 vs ×2) is what matters.
Two words first. Searching means finding where (or whether) a value is in a collection. Sorting means putting items in order. A list is sorted when every item is less than or equal to the next.
Q1: Binary search, first and last occurrence
Real-life example: a railway enquiry counter has a chart of one million booked PNR numbers (the number on a train ticket), sorted from smallest to largest. 200 people ask "is my PNR booked?". Reading the chart from the top for each of them is hopeless. You'd open it in the middle, see whether your number is bigger or smaller, and throw away half.
Attempt 1: in on a list
random.seed(7) makes the "random" numbers the same on every run. random.sample(range(N), k) picks k different numbers. time.perf_counter() is a precise clock for timing code.
import time, random
random.seed(7)
tickets = sorted(random.sample(range(10_000_000), 1_000_000))
asks = random.sample(range(10_000_000), 200) # 200 enquiries
start = time.perf_counter()
found = sum(1 for t in asks if t in tickets)
print(found, "of 200 found")
print(f"{time.perf_counter() - start:.2f} s")
Output:
20 of 200 found
3.52 s
Why it is slow: x in some_list is linear search: it checks the items one by one from the start. A missing PNR means checking all 1,000,000. That is O(n) per question, and it ignores the fact that the list is sorted.
Binary search: halve the range
Keep two ends, lo and hi, and look at the middle, mid = (lo + hi) // 2:
a[mid] == target: found;a[mid] < target: the target can only be to the right:lo = mid + 1;a[mid] > target: it can only be to the left:hi = mid - 1.
Each step throws away half: 1,000,000 → 500,000 → 250,000 → ... → 1 in about 20 steps (log₂ 1,000,000 ≈ 20). That is O(log n). It only works on sorted data.
import time, random
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1 # throw away the left half
else:
hi = mid - 1 # throw away the right half
return -1
random.seed(7)
tickets = sorted(random.sample(range(10_000_000), 1_000_000))
asks = random.sample(range(10_000_000), 200)
start = time.perf_counter()
found = sum(1 for t in asks if binary_search(tickets, t) != -1)
print(found, "of 200 found")
print(f"{time.perf_counter() - start:.4f} s")
marks = [35, 50, 72, 72, 72, 72, 90]
print(binary_search(marks, 72))
Output:
20 of 200 found
0.0008 s
3
Same answer, thousands of times faster. But for marks, 72 first appears at index 2, and binary search returned 3: it stops at whichever 72 mid lands on first.
First and last occurrence
On a hit, save it and keep going: for the first one, keep searching to the left (hi = mid - 1); for the last one, to the right (lo = mid + 1). The count of a value is last - first + 1. Still O(log n).
index: 0 1 2 3 4 5 6
marks: 35 50 72 72 72 72 90
^first ^last
def find(a, target, first):
lo, hi, ans = 0, len(a) - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
ans = mid # save it, keep going
if first:
hi = mid - 1 # look left
else:
lo = mid + 1 # look right
elif a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return ans
marks = [35, 50, 72, 72, 72, 72, 90]
print(find(marks, 72, True), find(marks, 72, False))
print(find(marks, 60, True), find(marks, 60, False))
print(find([], 5, True), find([72], 72, True))
Output:
2 5
-1 -1
-1 0
The library way: bisect
bisect_left(a, x): the first position wherexcould be inserted keepingasorted, i.e. the index of the firstxif it is there;bisect_right(a, x): the position just after the lastx;bisect_right - bisect_left= how many timesxappears;insort(a, x): insertsxin the right place. Finding the place is O(log n), but shifting the later items is O(n).
from bisect import bisect_left, bisect_right, insort
marks = [35, 50, 72, 72, 72, 72, 90]
left = bisect_left(marks, 72) # first position of 72
right = bisect_right(marks, 72) # just after the last 72
print(left, right - 1, "count:", right - left)
print(bisect_left(marks, 60)) # where 60 would go
insort(marks, 60) # insert, keep it sorted
print(marks)
Output:
2 5 count: 4
2
[35, 50, 60, 72, 72, 72, 72, 90]
To check membership with bisect, test the position too:
from bisect import bisect_left
def contains(a, x):
i = bisect_left(a, x)
return i < len(a) and a[i] == x
marks = [35, 50, 72, 72, 72, 72, 90]
print(contains(marks, 72), contains(marks, 60), contains(marks, 100))
Output:
True False False
If you only need "is it there?" and don't need order, a set is even simpler: x in some_set is O(1) on average (episode 20 explained hashing).
Q2: Merge sort
Real-life example: two teachers each have a pile of answer sheets already sorted by roll number. To make one sorted pile, look at the top sheet of each pile and take the smaller roll number, again and again: one pass. And a big unsorted pile? Split it in half, sort each half the same way, then merge them.
Attempt 1: bubble sort
Bubble sort walks through the list swapping neighbours that are in the wrong order, n times. a = a[:] makes a copy so the caller's list is not changed.
import time, random
def bubble_sort(a):
a = a[:]
n = len(a)
for i in range(n):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return a
print(bubble_sort([42, 7, 19, 3, 25]))
for n in [2000, 4000, 8000]:
data = [random.randint(1, 10**6) for _ in range(n)]
start = time.perf_counter()
bubble_sort(data)
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
[3, 7, 19, 25, 42]
2000 0.12 s
4000 0.47 s
8000 1.81 s
Why it is slow: two nested loops make about n × n / 2 comparisons: O(n²). Doubling the input makes it about four times slower. A million items would be about 500 billion comparisons: days in Python.
Merging two sorted lists
Two pointers (indexes) i and j, one per pile. Take the smaller front item. <= takes from the left pile on a tie, which keeps equal items in their original order (that makes the sort stable). When one pile is empty, add the rest of the other.
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps ties in order
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]) # one pile is empty:
out.extend(right[j:]) # add what's left of the other
return out
print(merge([3, 19, 42], [7, 25]))
print(merge([], [5, 8]))
Output:
[3, 7, 19, 25, 42]
[5, 8]
Merge sort
[42 7 19 3 25]
split [42 7] [19 3 25]
sort halves [7 42] [3 19 25]
merge [3 7 19 25 42]
- Base case: 0 or 1 items is already sorted.
- Recursive case: split at
mid,merge_sorteach half,mergethem.
Halving gives about log₂ n levels; at each level, the merges together touch every item once, O(n). Total: O(n log n) time and O(n) extra space. This "split, solve, combine" pattern is called divide and conquer. The recursion depth is only log₂ n (about 20 for a million items), so there is no RecursionError.
import time, random
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
def merge_sort(a):
if len(a) <= 1: # base case: already sorted
return a
mid = len(a) // 2
return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))
print(merge_sort([42, 7, 19, 3, 25]))
print(merge_sort([]), merge_sort([5, 5, 1]))
for n in [8000, 100_000, 500_000]:
data = [random.randint(1, 10**6) for _ in range(n)]
start = time.perf_counter()
result = merge_sort(data)
secs = time.perf_counter() - start
print(n, f"{secs:.2f} s", result == sorted(data))
Output:
[3, 7, 19, 25, 42]
[] [1, 5, 5]
8000 0.01 s True
100000 0.20 s True
500000 1.21 s True
In real code: sorted() and list.sort()
Python's built-in sort is Timsort, a merge-sort relative written in C. It is O(n log n), stable, and very fast on data that is already partly sorted. sorted(x) returns a new list; x.sort() sorts in place and returns None.
import time, random
data = [random.randint(1, 10**6) for _ in range(500_000)]
start = time.perf_counter()
result = sorted(data)
print(f"sorted(): {time.perf_counter() - start:.3f} s")
nums = [3, 1, 2]
print(nums.sort(), nums) # sort() returns None
Output:
sorted(): 0.086 s
None [1, 2, 3]
| Algorithm | Time | Extra space | Stable |
|---|---|---|---|
| Linear search | O(n) | O(1) | |
| Binary search / bisect | O(log n) | O(1) | |
| Bubble sort | O(n²) | O(1) | yes |
| Merge sort | O(n log n) | O(n) | yes (with <=) |
sorted() (Timsort) |
O(n log n) | O(n) | yes |
Q3: Sort records by two keys
Real-life example: a teacher's rank list: marks from high to low, and on equal marks, names A to Z. A key is the value you sort by. Here there are two: marks (the primary key) and name (the secondary key).
Attempt 1: sort by marks, then sort by name
key=lambda s: s[1] tells sorted to compare each record's item 1 (the marks). reverse=True sorts high to low.
students = [("Ravi", 82), ("Asha", 91), ("Neha", 82),
("Kabir", 91), ("Priya", 75)]
# rank: marks high to low, then name A to Z
by_marks = sorted(students, key=lambda s: s[1], reverse=True)
ranked = sorted(by_marks, key=lambda s: s[0])
for s in ranked:
print(s)
Output:
('Asha', 91)
('Kabir', 91)
('Neha', 82)
('Priya', 75)
('Ravi', 82)
The result is simply alphabetical: Priya (75) is above Ravi (82). Why: the last sort decides the whole order. The first sort only matters among students with the same name.
Fix 1: one sort with a tuple key
Tuples compare item by item: the first items decide, and only on a tie does Python look at the second. -s[1] turns "marks high to low" into "small numbers first", so no reverse is needed.
students = [("Ravi", 82), ("Asha", 91), ("Neha", 82),
("Kabir", 91), ("Priya", 75)]
ranked = sorted(students, key=lambda s: (-s[1], s[0]))
for s in ranked:
print(s)
print((91, "Kabir") < (91, "Neha")) # item by item
low_marks_z_to_a = sorted(students, key=lambda s: (s[1], -s[0]))
Output:
('Asha', 91)
('Kabir', 91)
('Neha', 82)
('Ravi', 82)
('Priya', 75)
True
Traceback (most recent call last):
File "main.py", line 9, in <module>
low_marks_z_to_a = sorted(students, key=lambda s: (s[1], -s[0]))
File "main.py", line 9, in <lambda>
low_marks_z_to_a = sorted(students, key=lambda s: (s[1], -s[0]))
^^^^^
TypeError: bad operand type for unary -: 'str'
-s[0] fails: strings have no minus. Unary minus means a minus with one operand (-x).
Fix 2: two stable sorts, least important key first
A sort is stable when items with equal keys keep the order they already had. Python's sort is always stable. So sort by the secondary key first and the primary key last; each sort can have its own reverse.
students = [("Ravi", 82), ("Asha", 91), ("Neha", 82),
("Kabir", 91), ("Priya", 75)]
# marks low to high, then name Z to A: two stable sorts
# 1) the less important key first: name, Z to A
step1 = sorted(students, key=lambda s: s[0], reverse=True)
# 2) the main key last: marks
step2 = sorted(step1, key=lambda s: s[1])
for s in step2:
print(s)
from operator import itemgetter
print(sorted(students, key=itemgetter(1, 0))[:2])
Output:
('Priya', 75)
('Ravi', 82)
('Neha', 82)
('Kabir', 91)
('Asha', 91)
[('Priya', 75), ('Neha', 82)]
operator.itemgetter(1, 0) is a ready-made key returning (s[1], s[0]). It does the same as lambda s: (s[1], s[0]), a little faster.
Which fix to use: when every key you need to reverse is a number, one sort with a tuple key and minus signs is simplest. When a text key must go Z to A, use two stable sorts.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
x in big_list many times |
seconds for 200 lookups | linear search, O(n) each | sort once + bisect, or a set |
| binary search on unsorted data | wrong answers, no error | halving assumes sorted order | sort first |
mid = (lo + hi) // 2 with lo = mid / hi = mid |
an endless loop | the range stops shrinking | lo = mid + 1, hi = mid - 1 |
while lo < hi with hi = len(a) - 1 |
the last candidate is never checked | off by one | while lo <= hi |
| stopping at the first hit | index 3, not the first 72 (2) | mid can land on any copy |
save ans, keep going |
insort in a loop on a huge list |
slow | each insert shifts items: O(n) | collect, then sort once |
| bubble sort on big data | ×4 time for ×2 data | O(n²) | merge sort / sorted() |
merge with < instead of <= |
equal items swap order | not stable | <= |
nums = nums.sort() |
nums is None |
sort() returns None |
nums.sort() or nums = sorted(nums) |
| sort by key 1, then by key 2 | ordered by key 2 only | the last sort wins | tuple key, or secondary key first |
key=lambda s: -s[0] on names |
TypeError: bad operand type for unary -: 'str' |
no minus for text | two stable sorts |
Your turn: the integer square root (solution)
Question: isqrt(n): the largest whole number r with r * r <= n, using binary search, without math.sqrt.
Idea: the answer is between 0 and n. If mid * mid <= n, mid is a candidate: save it and search to the right for a bigger one. Otherwise search left. O(log n) steps; Python's big integers make it exact even for 10**18 (floating point n ** 0.5 can be off by one for huge numbers).
import math
def isqrt(n):
lo, hi, ans = 0, n, 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= n:
ans = mid # a candidate; try bigger
lo = mid + 1
else:
hi = mid - 1
return ans
print(isqrt(26), isqrt(25), isqrt(0), isqrt(1))
print(isqrt(10**18), isqrt(10**18 - 1))
print(all(isqrt(n) == math.isqrt(n) for n in range(10_000)))
Output:
5 5 0 1
1000000000 999999999
True
math.isqrt (episode 2) is the built-in.
Mini project: a cut-off list
An admissions office has every applicant's score, sorted. For each cut-off it needs how many applicants are at or above it, instantly, and the merit list sorted by score (high to low), then name.
from bisect import bisect_left
applicants = [("Asha", 91), ("Ravi", 82), ("Neha", 82), ("Kabir", 91),
("Priya", 75), ("Arjun", 68), ("Meera", 88)]
scores = sorted(score for _, score in applicants)
print("scores:", scores)
for cutoff in [70, 82, 90, 95]:
at_or_above = len(scores) - bisect_left(scores, cutoff)
print(f"cut-off {cutoff}: {at_or_above} applicants")
merit = sorted(applicants, key=lambda a: (-a[1], a[0]))
for rank, (name, score) in enumerate(merit, start=1):
print(rank, name, score)
Output:
scores: [68, 75, 82, 82, 88, 91, 91]
cut-off 70: 6 applicants
cut-off 82: 5 applicants
cut-off 90: 2 applicants
cut-off 95: 0 applicants
1 Asha 91
2 Kabir 91
3 Meera 88
4 Neha 82
5 Ravi 82
6 Priya 75
7 Arjun 68
Practice questions (with solutions)
1. Search in a rotated sorted list. [40, 50, 60, 10, 20, 30] is a sorted list rotated. Find the index of a target in O(log n).
Solution
At every mid, at least one half is sorted. Check whether the target lies inside the sorted half; if so, search there, otherwise search the other half.
def search_rotated(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[lo] <= a[mid]: # left half is sorted
if a[lo] <= target < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if a[mid] < target <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
a = [40, 50, 60, 10, 20, 30]
print([search_rotated(a, t) for t in [40, 60, 10, 30, 35]])
Output:
[0, 2, 3, 5, -1]
2. Count inversions with merge sort. An inversion is a pair i < j with a[i] > a[j] (how "unsorted" a list is). Count them in O(n log n).
Solution
During the merge, when an item from the right half is taken before the remaining items of the left half, it forms an inversion with each of them: add len(left) - i.
def sort_count(a):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
out, i, j, inv = [], 0, 0, x + y
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
inv += len(left) - i # right[j] < every left[i:]
out += left[i:] + right[j:]
return out, inv
print(sort_count([2, 4, 1, 3, 5])[1]) # (2,1) (4,1) (4,3)
print(sort_count([5, 4, 3, 2, 1])[1], sort_count([1, 2, 3])[1])
Output:
3
10 0
3. Sort words by length, then alphabetically.
Solution
words = ["chai", "dosa", "idli", "vada", "samosa", "poha", "upma", "pav"]
print(sorted(words, key=lambda w: (len(w), w)))
print(sorted(words, key=lambda w: (-len(w), w))) # longest first
Output:
['pav', 'chai', 'dosa', 'idli', 'poha', 'upma', 'vada', 'samosa']
['samosa', 'chai', 'dosa', 'idli', 'poha', 'upma', 'vada', 'pav']
4. Find the first element greater than a value (the "next higher price") in a sorted list.
Solution
bisect_right gives the position just after every copy of x, so the item there (if any) is the first one greater.
from bisect import bisect_right
prices = [10, 20, 20, 35, 50]
for x in [20, 34, 50, 5]:
i = bisect_right(prices, x)
print(x, "->", prices[i] if i < len(prices) else None)
Output:
20 -> 35
34 -> 35
50 -> None
5 -> 10
5. Merge k sorted lists.
Solution
heapq.merge merges any number of sorted inputs lazily in O(N log k), where N is the total number of items. (Merging them one by one with our merge also works but is slower for many lists.)
import heapq
sections = [[3, 19, 42], [7, 25], [1, 8, 30, 50]]
print(list(heapq.merge(*sections)))
Output:
[1, 3, 7, 8, 19, 25, 30, 42, 50]
Quick quiz
What does this print?
from bisect import bisect_left, bisect_right
a = [10, 20, 20, 20, 30]
x = bisect_left(a, 20)
y = bisect_right(a, 20)
z = bisect_left(a, 25)
print(x, y, z)
(A) 1 3 4 (B) 1 4 4 (C) 1 4 3 (D) 2 3 4
Answer
(B). bisect_left(a, 20) is the first 20, index 1. bisect_right(a, 20) is just after the last 20, index 4. 25 would go just before 30, also index 4.
from bisect import bisect_left, bisect_right
a = [10, 20, 20, 20, 30]
x = bisect_left(a, 20)
y = bisect_right(a, 20)
z = bisect_left(a, 25)
print(x, y, z)
Output:
1 4 4
Interview questions
- What is the time complexity of binary search, and what does it need? O(log n); the data must be sorted (and support fast indexing, like a list).
- How do you find the first occurrence of a repeated value? Binary search, and on a hit save the index and continue searching left (
hi = mid - 1). Orbisect_left. - How do you count occurrences of x in a sorted list in O(log n)?
bisect_right(a, x) - bisect_left(a, x). - Why can binary search loop forever? If
loorhiis set tomidinstead ofmid ± 1, the range can stop shrinking. - Explain merge sort and its complexity. Split in half, sort each half recursively, merge the sorted halves in one pass. O(n log n) time in every case, O(n) extra space, stable.
- Why is bubble sort O(n²)? Two nested loops over the data: about n²/2 comparisons.
- What does stable mean, and why does it matter? Equal keys keep their original order, which lets you sort by several keys with several passes.
- What sort does Python use? Timsort: a hybrid of merge sort and insertion sort, O(n log n), stable, fast on partly sorted data.
- How do you sort by two keys in different directions? A tuple key with negated numbers (
(-marks, name)), or two stable sorts with the secondary key first. sorted(x)vsx.sort()?sortedreturns a new list and works on any iterable;list.sortsorts in place and returnsNone.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Searching | Finding where (or whether) a value is in a collection | is PNR 7 booked? |
| Sorting | Putting items in order | sorted([3, 1, 2]) |
| Sorted list | Every item ≤ the next | [35, 50, 72] |
| Linear search | Checking items one by one, O(n) | x in list |
| Binary search | Halving a sorted range each step, O(log n) | lo, mid, hi |
lo / hi / mid |
The ends and the middle of the range still possible | mid = (lo + hi) // 2 |
| O(log n) | Steps grow by one when n doubles | 20 steps for a million |
| First / last occurrence | The smallest / largest index of a repeated value | 2 and 5 for 72 |
bisect_left |
Insert position before any equal items | bisect_left(a, 72) |
bisect_right |
Insert position after any equal items | bisect_right(a, 72) |
insort |
Insert keeping the list sorted | insort(a, 60) |
random.seed |
Makes random numbers repeatable | random.seed(7) |
random.sample |
k different random items | random.sample(range(10), 3) |
time.perf_counter |
A precise clock for timing | end - start |
| PNR | Passenger Name Record: the number on a train ticket | 4521378 |
| Bubble sort | Repeatedly swap wrong-order neighbours, O(n²) | |
| O(n²) | Doubling n makes it about 4× slower | nested loops |
| Pointer (index) | A variable marking a position | i, j in merge |
| Merge | Combine two sorted lists into one, O(n) | merge([3, 19], [7]) |
| Merge sort | Split, sort halves, merge: O(n log n) | merge_sort(a) |
| Divide and conquer | Split a problem, solve the parts, combine | merge sort |
| O(n log n) | The cost of good comparison sorts | a million items ≈ 20 million steps |
| Timsort | Python's built-in sort algorithm | sorted(), list.sort() |
| Key | The value a sort compares | key=lambda s: s[1] |
| Primary / secondary key | The main order / the tie-breaker | marks / name |
| Tuple key | A key returning a tuple, compared item by item | (-s[1], s[0]) |
reverse=True |
Sort from high to low | sorted(x, reverse=True) |
| Unary minus | A minus with one operand | -x |
| Stable sort | Equal keys keep their existing order | Python's sort |
operator.itemgetter |
A ready-made key picking items | itemgetter(1, 0) |
| Inversion | A pair in the wrong order | (4, 1) in [4, 1] |
heapq.merge |
Merge many sorted inputs | heapq.merge(a, b, c) |
Summary
x in listis linear search: O(n). On sorted data, binary search halves the range each step: about 20 steps for a million items, O(log n).- For the first/last occurrence, save the hit and keep searching left/right, or use
bisect_left/bisect_right; their difference is the count.insortinserts in order. - Bubble sort is O(n²): doubling the data quadruples the time. Merge sort splits, sorts the halves recursively and merges them in one pass: O(n log n), O(n) space, stable with
<=. In real code usesorted()/list.sort()(Timsort). - Two keys: one sort with a tuple key (
(-marks, name)), or, when a string needs reversing, two stable sorts with the less important key first. - Next episode: linked list questions: a
Nodeclass, reversing a linked list, the middle node with slow and fast pointers, and detecting a cycle.