SyntaxPilot
Courses/Python Coding Questions/Lesson 22
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 22 of 30

Searching and sorting questions

binary search (first and last occurrence, bisect)merge sortsort records by two keys (key=lambda with a tuple, stability)

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 where x could be inserted keeping a sorted, i.e. the index of the first x if it is there;
  • bisect_right(a, x): the position just after the last x;
  • bisect_right - bisect_left = how many times x appears;
  • insort(a, x): inserts x in 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_sort each half, merge them.

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

  1. 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).
  2. 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). Or bisect_left.
  3. How do you count occurrences of x in a sorted list in O(log n)? bisect_right(a, x) - bisect_left(a, x).
  4. Why can binary search loop forever? If lo or hi is set to mid instead of mid ± 1, the range can stop shrinking.
  5. 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.
  6. Why is bubble sort O(n²)? Two nested loops over the data: about n²/2 comparisons.
  7. 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.
  8. What sort does Python use? Timsort: a hybrid of merge sort and insertion sort, O(n log n), stable, fast on partly sorted data.
  9. 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.
  10. sorted(x) vs x.sort()? sorted returns a new list and works on any iterable; list.sort sorts in place and returns None.

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 list is 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. insort inserts 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 use sorted() / 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 Node class, reversing a linked list, the middle node with slow and fast pointers, and detecting a cycle.