SyntaxPilot
Courses/Python/Lesson 37
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 · Lesson 37 of 40

DSA 4: sorting, binary search, two pointers

queued

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.lower sorts by the lowercase version of each name.
  • key=len, reverse=True sorts 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

  1. Write binary_search_count(a, x) that returns the index and the number of middle checks. Try it on list(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).

  1. 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.

  1. 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
  1. Write first_at_least(prices, budget) that returns the cheapest price that is at least budget, using bisect_left, or None.
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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. sorted(a) vs a.sort()? sorted returns a new list and works on any iterable; a.sort() changes the list in place and returns None.
  6. 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".
  7. How do you avoid an infinite loop in binary search? Make sure the range shrinks every step: lo = mid + 1 and hi = mid - 1, with while 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, then bisect for fast lookups. list.sort() returns None.
  • 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.