These are the notes for Python episode 37, part four of data structures and algorithms. Raju's app has a million orders and a customer wants one of them right now. Checking one by one (linear search) takes up to a million steps, so you invent binary search and find any order in about 20. Binary search only works on sorted data, so you invent bubble sort, watch it slow down as O(n²), and then invent merge sort, which is O(n log n). Then you meet Python's own tools (sorted(), list.sort(), key=, bisect) and finish with the two pointers technique for Raju's ₹500 combo coupon. Every program below ran for real (Python 3.13.18).
The problem: one order in a million
Raju's order ids run from 100000 to 1099999, stored in a list in order. A customer calls: "Where is order 834219?" The obvious way is to start at the first order and check each one. That is linear search.
orders = list(range(100000, 1100000)) # a million order ids, in order
def find(orders, target):
steps = 0
for i, order in enumerate(orders):
steps += 1
if order == target:
return i, steps
return -1, steps
print(find(orders, 834219))
print(find(orders, 1099999))
print(find(orders, 5)) # not there at all
Output:
(734219, 734220)
(999999, 1000000)
(-1, 1000000)
- Order 834219 needs 734,220 steps.
- The last order needs a full million.
- An order that is not there also costs a million steps, because you can only say "no" after checking everything.
Linear search is O(n): the work grows in step with the list. With thousands of support calls a day, that's billions of steps. And it ignores a gift: the ids are already in order.
Binary search: open the middle
Real-life example: finding a word in a paper dictionary. You never start at page one. You open near the middle (say "M"). "Python" comes after "M", so the whole first half is gone in one look. Then you open the middle of what's left, and repeat. Or the guessing game: "a number from 1 to 100" — guess 50, hear "higher", and half the range is gone.
That's binary search: keep two indexes, lo (the first index still possible) and hi (the last), look at the middle mid = (lo + hi) // 2, and throw away the half that can't contain the target.
Tracing a search for 63 in [12, 19, 27, 34, 41, 56, 63, 78, 85, 92]:
| Step | lo | hi | mid | orders[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 41 | 41 < 63 → lo = 5 |
| 2 | 5 | 9 | 7 | 78 | 78 > 63 → hi = 6 |
| 3 | 5 | 6 | 5 | 56 | 56 < 63 → lo = 6 |
| 4 | 6 | 6 | 6 | 63 | found at index 6 |
orders = list(range(100000, 1100000)) # sorted order ids
def binary_search(orders, target):
lo, hi, steps = 0, len(orders) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2 # open the middle page
if orders[mid] == target:
return mid, steps
elif orders[mid] < target:
lo = mid + 1 # throw away the left half
else:
hi = mid - 1 # throw away the right half
return -1, steps
print(binary_search(orders, 834219))
print(binary_search(orders, 1099999))
print(binary_search(orders, 5))
Output:
(734219, 20)
(999999, 20)
(-1, 19)
Twenty steps instead of 734,220. A missing order is reported in 19 steps. Each step halves the range, and 2²⁰ ≈ 1,000,000, so a million items need about 20 halvings. That's O(log n).
| Items | Linear search (worst) | Binary search (worst) |
|---|---|---|
| 1,000 | 1,000 | about 10 |
| 1,000,000 | 1,000,000 | about 20 |
| 1,000,000,000 | 1,000,000,000 | about 30 |
Double the data and binary search needs just one more step.
Binary search needs sorted data
def binary_search(items, target):
lo, hi = 0, len(items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
orders = [507, 112, 938, 341, 760, 205, 689] # as they arrived
print(205 in orders)
print(binary_search(orders, 205))
Output:
True
-1
in says the order is there; binary search says -1. The first middle is 341; 205 is smaller, so the search throws away the right half — exactly where 205 was. No error, just a wrong answer. Throwing half away is only safe when the list is sorted. So before searching fast, we need to sort.
Bubble sort: compare neighbours, swap
Real-life example: a teacher arranging exam papers by roll number. Walk along the pile, compare two neighbouring papers, swap them if they're in the wrong order. After one full pass, the biggest roll number has "bubbled" to the end. Repeat with shorter passes until everything is in place.
import random
random.seed(7)
def bubble_sort(items):
items = items[:]
comparisons = 0
for end in range(len(items) - 1, 0, -1):
for i in range(end):
comparisons += 1
if items[i] > items[i + 1]: # wrong order? swap
items[i], items[i + 1] = items[i + 1], items[i]
return items, comparisons
small = [507, 112, 938, 341, 760]
print(bubble_sort(small))
for n in [1000, 2000, 4000]:
orders = [random.randint(1, 10**6) for _ in range(n)]
result, comps = bubble_sort(orders)
print(n, "orders:", comps, "comparisons")
Output:
([112, 341, 507, 760, 938], 10)
1000 orders: 499500 comparisons
2000 orders: 1999000 comparisons
4000 orders: 7998000 comparisons
| Orders (n) | Comparisons | Growth |
|---|---|---|
| 1,000 | 499,500 | — |
| 2,000 | 1,999,000 | × 4 |
| 4,000 | 7,998,000 | × 4 |
Bubble sort always does n(n−1)/2 comparisons. Double the orders and the work goes up four times: that's O(n²). For a million orders it would be about 500 billion comparisons.
Merge sort: split, then merge
Real-life example: a smarter teacher splits the pile in two and hands each half to a helper, who splits again, until every pile has one paper. A pile of one is already sorted (the base case, as in recursion from episode 15). Then the piles are merged: two sorted piles become one by always taking the smaller of the two top papers.
Merging [112, 507, 938] and [341, 760]:
| Compare | Take | Merged so far |
|---|---|---|
| 112 vs 341 | 112 | 112 |
| 507 vs 341 | 341 | 112, 341 |
| 507 vs 760 | 507 | 112, 341, 507 |
| 938 vs 760 | 760 | 112, 341, 507, 760 |
| (right pile empty) | 938 | 112, 341, 507, 760, 938 |
Merging n papers takes about n steps, and halving gives about log₂ n levels, so merge sort is O(n log n).
import random
random.seed(7)
comparisons = 0
def merge(left, right): # two sorted piles -> one
global comparisons
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
comparisons += 1
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
def merge_sort(items):
if len(items) <= 1: # one paper is already sorted
return items
mid = len(items) // 2
return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([507, 112, 938, 341, 760]))
for n in [1000, 2000, 4000]:
comparisons = 0
orders = [random.randint(1, 10**6) for _ in range(n)]
assert merge_sort(orders) == sorted(orders)
print(n, "orders:", comparisons, "comparisons")
Output:
[112, 341, 507, 760, 938]
1000 orders: 8697 comparisons
2000 orders: 19386 comparisons
4000 orders: 42859 comparisons
| Orders (n) | Bubble sort | Merge sort |
|---|---|---|
| 1,000 | 499,500 | 8,697 |
| 2,000 | 1,999,000 | 19,386 |
| 4,000 | 7,998,000 | 42,859 |
| 1,000,000 | ~500,000,000,000 | ~20,000,000 |
The assert passed silently, so every result matched Python's sorted().
Python's tools: sorted(), list.sort(), key= and bisect
In real code you don't write your own sort. sorted() uses Timsort, a tuned merge sort (with insertion sort for short runs) written in C. It is stable: items that compare equal keep their original order.
import random, time
random.seed(7)
orders = [random.randint(1, 10**9) for _ in range(1_000_000)]
start = time.perf_counter()
fast = sorted(orders) # a new sorted list
print("sorted 1,000,000 orders in", round(time.perf_counter() - start, 2), "s")
print(fast[:3], fast == sorted(fast))
names = ["Priya", "asha", "Ravi", "Neha"]
print(sorted(names))
print(sorted(names, key=str.lower))
print(sorted(names, key=len, reverse=True))
Output:
sorted 1,000,000 orders in 0.25 s
[256, 2531, 2721] True
['Neha', 'Priya', 'Ravi', 'asha']
['asha', 'Neha', 'Priya', 'Ravi']
['Priya', 'asha', 'Ravi', 'Neha']
(The time printed depends on the machine; it's always a fraction of a second.)
- Plain
sorted(names)puts'asha'last: capital letters come before small letters in character order. key=str.lowersorts by the lowercase version of each name.key=len, reverse=Truesorts by length, longest first. The key is a function that says what to sort by.
list.sort() returns None
prices = [120, 40, 250, 90]
prices = prices.sort()
print(prices[0])
Output:
Traceback (most recent call last):
File "main.py", line 3, in <module>
print(prices[0])
~~~~~~^^^
TypeError: 'NoneType' object is not subscriptable
list.sort() sorts the list in place and returns None, so prices became None. Use prices.sort() on its own line, or prices = sorted(prices).
bisect: binary search, built in
prices = [120, 40, 250, 90]
prices.sort() # sorts in place, returns None
print(prices[0])
from bisect import bisect_left
orders = list(range(100000, 1100000))
i = bisect_left(orders, 834219) # binary search, built in
print(i, orders[i])
Output:
40
734219 834219
bisect_left(a, x) returns the index where x is, or where it would be inserted to keep a sorted. Check i < len(a) and a[i] == x to know whether x is really there. The rule: sort once with sorted(), then search as often as you like with bisect.
Two pointers: the ₹500 combo
Raju's coupon needs two items that cost exactly ₹500 together. The obvious way: try every pair.
prices = [40, 60, 90, 120, 150, 180, 250, 300, 350, 410]
coupon = 500
def combo_brute(prices, total):
checks = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
checks += 1
if prices[i] + prices[j] == total:
return prices[i], prices[j], checks
return None, None, checks
print(combo_brute(prices, coupon))
big = list(range(1, 8001)) # 8,000 items on the shelf
print(combo_brute(big, 15999))
Output:
(90, 410, 24)
(7999, 8000, 31996000)
8,000 items took 31,996,000 checks: every item is paired with every other, O(n²).
Real-life example: two hands on a shelf sorted by price. Left hand on the cheapest, right hand on the costliest. Too little? The only way to add money is to move the left hand up. Too much? Move the right hand down. Each move rules out an item for good, so the hands meet after at most n moves.
| Check | left | right | Sum | Move |
|---|---|---|---|---|
| 1 | 40 | 410 | 450 | too little → left + 1 |
| 2 | 60 | 410 | 470 | too little → left + 1 |
| 3 | 90 | 410 | 500 | found |
def combo(prices, total): # prices must be sorted
left, right, checks = 0, len(prices) - 1, 0
while left < right:
checks += 1
s = prices[left] + prices[right]
if s == total:
return prices[left], prices[right], checks
elif s < total:
left += 1 # need more: cheaper side moves up
else:
right -= 1 # too much: costlier side comes down
return None, None, checks
prices = [40, 60, 90, 120, 150, 180, 250, 300, 350, 410]
print(combo(prices, 500))
big = list(range(1, 8001))
print(combo(big, 15999))
print(combo(prices, 1000))
Output:
(90, 410, 3)
(7999, 8000, 7999)
(None, None, 9)
7,999 checks instead of 31,996,000: O(n) after sorting (O(n log n) if you have to sort first). Sorting the data first unlocked a much faster algorithm — the theme of this whole episode.
Complexity summary
| Task | Algorithm | Time | Extra space |
|---|---|---|---|
| Search, unsorted | linear search (x in list) |
O(n) | O(1) |
| Search, sorted | binary search / bisect |
O(log n) | O(1) |
| Sort | bubble sort | O(n²) | O(1) |
| Sort | merge sort | O(n log n) | O(n) |
| Sort | sorted() / list.sort() (Timsort) |
O(n log n) | O(n) |
| Pair with a sum | every pair | O(n²) | O(1) |
| Pair with a sum, sorted | two pointers | O(n) | O(1) |
| Membership only | set (episode 35) |
O(1) average | O(n) |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Binary search on unsorted data | -1 for an item that exists |
it threw away the half that held it | sort first, or use in |
prices = prices.sort() |
TypeError: 'NoneType' object is not subscriptable |
.sort() returns None |
prices.sort() or sorted(prices) |
lo = mid instead of lo = mid + 1 |
the loop never ends | the range stops shrinking | lo = mid + 1, hi = mid - 1 |
while lo < hi with hi = len - 1 |
the last remaining item is never checked | the loop stops one step early | while lo <= hi |
| Nested loops over every pair | slow: 31,996,000 checks | O(n²) | sort, then two pointers |
| Sorting names with mixed capitals | 'asha' after 'Ravi' |
capitals sort before small letters | key=str.lower |
Mini project: Raju's order desk
Keep orders as (order_id, customer, amount) tuples, sort them once by id, look orders up with bisect, show the top 5 by amount, and find a combo for a coupon with two pointers. Count the steps.
from bisect import bisect_left
orders = [(507, "Asha", 240), (112, "Ravi", 90), (938, "Priya", 410),
(341, "Neha", 150), (760, "Raju", 60), (205, "Asha", 300), (689, "Ravi", 180)]
orders.sort(key=lambda o: o[0]) # sort once by order id
ids = [o[0] for o in orders] # bisect needs the keys alone
def lookup(order_id):
i = bisect_left(ids, order_id)
if i < len(ids) and ids[i] == order_id:
oid, name, amount = orders[i]
print(f"order {oid}: {name}, Rs {amount}")
else:
print(f"order {order_id}: not found")
def top(k):
for oid, name, amount in sorted(orders, key=lambda o: o[2], reverse=True)[:k]:
print(f" Rs {amount:>4} {name} (#{oid})")
def combo(total):
prices = sorted(o[2] for o in orders)
left, right, steps = 0, len(prices) - 1, 0
while left < right:
steps += 1
s = prices[left] + prices[right]
if s == total:
return prices[left], prices[right], steps
if s < total:
left += 1
else:
right -= 1
return None, None, steps
lookup(341)
lookup(999)
print("top 5 by amount:")
top(5)
print("combo for 500:", combo(500))
print("combo for 1000:", combo(1000))
Output:
order 341: Neha, Rs 150
order 999: not found
top 5 by amount:
Rs 410 Priya (#938)
Rs 300 Asha (#205)
Rs 240 Asha (#507)
Rs 180 Ravi (#689)
Rs 150 Neha (#341)
combo for 500: (90, 410, 2)
combo for 1000: (None, None, 6)
Practice
- Write
binary_search_count(a, x)that returns the index and the number of middle checks. Try it onlist(range(1, 1025))for 1 and 1024.
Solution
def binary_search_count(a, x):
lo, hi, steps = 0, len(a) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if a[mid] == x:
return mid, steps
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
a = list(range(1, 1025))
print(binary_search_count(a, 1))
print(binary_search_count(a, 1024))
print(binary_search_count(a, 5000))
Output:
(0, 10)
(1023, 11)
(-1, 11)
1,024 items never need more than 11 checks (2¹⁰ = 1,024).
- Sort orders by amount (highest first), and by customer name A to Z when amounts are equal.
Solution
orders = [("Ravi", 240), ("asha", 300), ("Neha", 240), ("Priya", 90)]
result = sorted(orders, key=lambda o: (-o[1], o[0].lower()))
print(result)
Output:
[('asha', 300), ('Neha', 240), ('Ravi', 240), ('Priya', 90)]
A tuple key sorts by the first item, then the second. -amount gives highest first without reverse=True, so names still go A to Z.
- Find three items whose prices add up to ₹500. Hint: sort, fix one item, then run two pointers on the rest. That's O(n²) instead of O(n³).
Solution
def three_sum(prices, total):
prices = sorted(prices)
for i in range(len(prices) - 2):
left, right = i + 1, len(prices) - 1
while left < right:
s = prices[i] + prices[left] + prices[right]
if s == total:
return prices[i], prices[left], prices[right]
if s < total:
left += 1
else:
right -= 1
return None
print(three_sum([250, 40, 180, 90, 60, 300, 110], 500))
print(three_sum([10, 20, 30], 500))
Output:
(90, 110, 300)
None
- Write
first_at_least(prices, budget)that returns the cheapest price that is at leastbudget, usingbisect_left, orNone.
Solution
from bisect import bisect_left
def first_at_least(prices, budget):
i = bisect_left(prices, budget)
return prices[i] if i < len(prices) else None
prices = [40, 60, 90, 120, 150, 180, 250]
print(first_at_least(prices, 100))
print(first_at_least(prices, 150))
print(first_at_least(prices, 999))
Output:
120
150
None
Quick quiz
nums = [3, 8, 15, 21, 30, 42, 57]
# binary search for 42
# how many times is the middle checked?
Options: 1 · 2 · 3 · 6
Answer
2. lo=0, hi=6 → mid=3, nums[3] is 21, too small → lo=4. mid=(4+6)//2=5, nums[5] is 42: found.
Interview questions
- Why does binary search need sorted input? It throws away half the range based on one comparison; that is only safe if everything on one side is smaller and everything on the other is bigger.
- What is the time complexity of binary search, and why? O(log n): each step halves the range, so after k steps n/2ᵏ items remain; it ends when that reaches 1, at k = log₂ n.
- Bubble sort vs merge sort? Bubble sort is O(n²) time, O(1) extra space, simple. Merge sort is O(n log n) time in every case and needs O(n) extra space for merging.
- What is a stable sort? One that keeps equal items in their original order. Timsort (
sorted) is stable, which lets you sort by one key and then another. sorted(a)vsa.sort()?sortedreturns a new list and works on any iterable;a.sort()changes the list in place and returnsNone.- When do two pointers work? When the data is sorted (or has some order) and moving one pointer can rule out items for good, as in "pair with a given sum".
- How do you avoid an infinite loop in binary search? Make sure the range shrinks every step:
lo = mid + 1andhi = mid - 1, withwhile lo <= hi.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Linear search | Check items one by one from the start | for order in orders: if order == target |
| Binary search | Look at the middle of a sorted range and throw away the half that can't hold the target | 20 steps for a million orders |
| lo, hi | The first and last index still possible in a binary search | lo, hi = 0, len(a) - 1 |
| mid | The middle index of the current range | mid = (lo + hi) // 2 |
Floor division // |
Division that rounds down to a whole number | 9 // 2 is 4 |
| O(n) | Work grows in step with the input size | linear search |
| O(log n) | Work grows by one step each time the input doubles | binary search |
| O(n²) | Work grows four times when the input doubles | bubble sort, every pair |
| O(n log n) | A little more than linear; the best general sorting can do | merge sort, sorted() |
| Sorting | Putting items in order (smallest first by default) | [112, 341, 507] |
| Bubble sort | Repeatedly compare neighbours and swap them if out of order | 7,998,000 comparisons for 4,000 items |
| Pass | One walk along the list in bubble sort | after pass 1, the biggest is last |
| Merge sort | Split the list in halves, sort each half, merge the sorted halves | 42,859 comparisons for 4,000 items |
| Merge | Combine two sorted lists into one by always taking the smaller front item | [112, 507] + [341] → [112, 341, 507] |
| Base case | The smallest input a recursive function answers directly | a list of one item is sorted |
| Timsort | Python's built-in sorting algorithm: a tuned, stable merge sort | used by sorted() and list.sort() |
| Stable sort | Equal items keep their original order | two ₹240 orders stay in input order |
sorted() |
Returns a new sorted list from any iterable | sorted([3, 1, 2]) |
list.sort() |
Sorts a list in place and returns None |
prices.sort() |
key= |
A function that says what to sort by | key=str.lower, key=len |
reverse=True |
Sort biggest first | sorted(a, reverse=True) |
| In place | Changing the original object instead of making a new one | list.sort() |
bisect_left |
Binary search from the bisect module: index where x is or would go |
bisect_left(ids, 834219) |
| Two pointers | Two indexes moving through sorted data (often from both ends) to rule items out | pair with sum 500 in 3 checks |
| Comparison | Checking which of two items is bigger | items[i] > items[i + 1] |
assert |
Stops with AssertionError if a condition is false; silent if true |
assert merge_sort(a) == sorted(a) |
Summary
- Linear search checks everything: O(n).
- Binary search halves the range each step: O(log n), about 20 steps for a million items — but only on sorted data, otherwise it silently gives wrong answers.
- Bubble sort compares neighbours: O(n²). Merge sort splits and merges: O(n log n).
- In real code:
sorted(data, key=...)once, thenbisectfor fast lookups.list.sort()returnsNone. - Two pointers on sorted data find a pair with a given sum in O(n) instead of O(n²).
- Next episode: dynamic programming — remember answers, and never solve the same thing twice.