Searching and sorting

Search and sorting choices depend on data shape, query frequency, mutation rate, and ordering requirements. Python's built-ins are highly optimized; implement an algorithm yourself to learn it or when a specialized contract requires it.

Linear search

Linear search works on any iterable and can stop at the first match:

from collections.abc import Callable, Iterable
from typing import TypeVar

T = TypeVar("T")


def find_first(items: Iterable[T], matches: Callable[[T], bool]) -> T | None:
    for item in items:
        if matches(item):
            return item
    return None

Time is O(n) in the worst case and space is O(1). It is often the right choice for one query over a small or unsorted collection.

Binary search

Binary search requires data sorted by the searched key. Use bisect for production code:

from bisect import bisect_left


def contains(sorted_values: list[int], target: int) -> bool:
    index = bisect_left(sorted_values, target)
    return index < len(sorted_values) and sorted_values[index] == target

The search is O(log n). Inserting into a list at the returned index remains O(n) because later elements must move.

An explicit implementation makes the invariant visible:

from collections.abc import Sequence


def binary_search(values: Sequence[int], target: int) -> int | None:
    low = 0
    high = len(values)

    while low < high:
        middle = low + (high - low) // 2
        candidate = values[middle]
        if candidate < target:
            low = middle + 1
        else:
            high = middle

    if low < len(values) and values[low] == target:
        return low
    return None

The half-open interval [low, high) avoids mixing inclusive and exclusive endpoints. This version returns the first matching position when duplicates exist.

Lookup indexes

For repeated exact queries, build a dictionary:

from dataclasses import dataclass


@dataclass(frozen=True)
class User:
    user_id: int
    name: str


def index_users(users: list[User]) -> dict[int, User]:
    return {user.user_id: user for user in users}

Building the index costs O(n) time and space; expected lookup is O(1). Decide explicitly what duplicate keys mean. The comprehension above silently keeps the last user.

Sorting with keys

Use sorted() to produce a new list and .sort() to mutate an existing list. Both use Timsort, are stable, and have worst-case O(n log n) time.

from operator import attrgetter

ordered = sorted(users, key=attrgetter("name", "user_id"))

Stability means equal keys retain their relative order. It enables multi-pass sorting:

records.sort(key=attrgetter("name"))
records.sort(key=attrgetter("department"))

The final order is by department, then name. A tuple key is usually clearer when all directions match.

Mixed directions and missing values

Avoid clever arithmetic for descending text or nullable fields. Make rules explicit:

from dataclasses import dataclass
from datetime import datetime


@dataclass(frozen=True)
class Event:
    name: str
    occurred_at: datetime | None


events.sort(
    key=lambda event: (
        event.occurred_at is None,
        event.occurred_at or datetime.min,
        event.name.casefold(),
    )
)

Missing dates sort last. If dates are timezone-aware, use a compatible aware fallback instead of datetime.min.

When not to sort

• Use min() or max() for one extreme: O(n) instead of sorting all values.
• Use heapq.nsmallest() or nlargest() for a small k.
• Use a set or dictionary for repeated exact membership tests.
• Let a database sort filtered data when transferring all rows would dominate cost.

Pitfalls

• binary searching data that is not sorted by the same key;
• sorting in place when callers expect the original order;
• key functions with side effects or expensive repeated work;
• forgetting Unicode normalization or case rules for human text;
• assuming dictionary lookup preserves a meaningful sorted order;
• implementing quicksort when built-in sorting is safer and faster.

Checklist

• The query pattern and data size are known.
• Duplicate and missing-key behavior is defined.
• Binary search uses the same ordering as the sort.
• Mutation from .sort() is intentional.
• Stability is used or documented where relevant.
• A full sort is necessary for the requested result.
• Human-language collation requirements are treated as a product decision.

Practice

Create 10,000 records with repeated names and unique IDs. Implement one exact lookup with a linear scan, repeated lookups with a dictionary, and prefix display with a sorted list. Measure index construction separately from queries and identify the query count at which the index pays for itself.