skip to content

In bisect, how does the key= parameter added in Python 3.10 treat the x argument?

level: middleimportance: nice to knowfreq 18%

answer

  1. It mirrors the key used by sorted()
  2. Applied to elements, not to everything
  3. The search functions want a bare key
  4. insort must receive the whole item
  5. Added in 3.10, keyword-only

basics

~20 s

The search functions apply key only to list elements, never to x, so you pass an already-extracted key such as 45. The insort functions are the exception: they apply key to the item being inserted.

solid answer

~40 s

Python 3.10 added `key=` to all six bisect functions. For `bisect_left` and `bisect_right` the key function is applied to each element it probes but **not** to `x` — so over a list of `(name, age)` rows sorted by age you call `bisect.bisect_left(rows, 45, key=lambda r: r[1])` and pass the bare number, because you are usually searching for a key you have no record for. `insort_left` and `insort_right` invert that: they must insert the whole item, so they call `key(x)` themselves to locate the position and then insert `x`. Mixing the two up fails loudly and immediately with `TypeError`, not silently. Before 3.10 the idiom was a parallel list of extracted keys, or a decorated list of `(key, record)` tuples.

code

python · 13 lines
python
import bisect

def age(row):
    return row[1]

rows = [("ann", 31), ("bob", 45), ("cy", 45), ("dee", 52)]

print(bisect.bisect_left(rows, 45, key=age))   # 1
print(bisect.bisect_right(rows, 45, key=age))  # 3

bisect.insort_left(rows, ("eve", 45), key=age)
print(rows)
# [('ann', 31), ('eve', 45), ('bob', 45), ('cy', 45), ('dee', 52)]

go deeper

for a junior

Know that bisect can search a list of records by one field without decorating the data, using the same style of key callable that sorted() takes. The exact left-versus-insort asymmetry is not expected of you yet.

for a middle

Explain that the search functions never apply key to x while insort must, and be able to write both calls correctly for a list of tuples. Naming 3.10 as the version that added it is the differentiating detail.

for a senior

Judge when key= is the right tool versus storing a precomputed sort key on the element: the callable runs on every probe, and a list sorted by one field but searched with a key extracting another is silently wrong with no exception.

for a principal

Weigh maintaining a keyed sorted list in application code against letting a store with a real index own the ordering, and set the codebase convention for representing sort keys so ordering assumptions are visible rather than implied by a lambda at each call site.

### The signature Since Python 3.10 every function in `bisect` accepts a keyword-only `key` argument: `bisect_left(a, x, lo=0, hi=len(a), *, key=None)` and likewise for `bisect_right`, `insort_left`, `insort_right` and the `bisect`/`insort` aliases. It defaults to `None`, meaning "compare the elements themselves". When supplied, it is a one-argument callable that extracts the comparison key from an element — the same shape as the `key` accepted by `sorted`, and it must agree with the ordering the list is already in. ### The asymmetry that gets asked about For the two **search** functions, the key is applied to elements drawn from the list and **not** to `x`. This is deliberate rather than an oversight. You typically search a table of records for a bare key — an age, a timestamp, an id — and you do not have a record to hand; requiring one would force you to fabricate a dummy object just to ask the question. For the two **insort** functions the situation is reversed by necessity. Their job is to insert the real item, so they cannot take a bare key: they compute `key(x)` internally, use it to find the position, and then insert the original `x`. So the very same argument slot means "a key" in `bisect_left` and "a whole item" in `insort_left`. ```python import bisect def age(row): return row[1] rows = [("ann", 31), ("bob", 45), ("cy", 45), ("dee", 52)] bisect.bisect_left(rows, 45, key=age) # 1 -> x is a key bisect.insort_left(rows, ("eve", 45), key=age) # x is a whole row ``` Getting it backwards is not a silent bug, which is the redeeming feature. Passing a record to `bisect_left` raises `TypeError: '<' not supported between instances of 'tuple' and 'int'`, because the extracted element key is compared against your tuple. Passing a bare key to `insort_left` raises `TypeError: 'int' object is not subscriptable` when the key function tries to extract from it. Both fail on the first call. ### What life looked like before 3.10 Two workarounds dominated, and both still appear in code you will read. The first keeps a **parallel list** of extracted keys alongside the records, bisects the key list, and indexes the record list with the same integer — correct but requiring every mutation to touch two lists in step, which is exactly the invariant that eventually breaks. The second **decorates** the data as `(key, record)` tuples so that ordinary tuple ordering compares the key first; searching then means constructing a probe tuple, and ties fall through to comparing the records themselves unless a tiebreaker sits in between. `key=` removes both the duplication and the fall-through hazard. ### Cost The key function is called once per element the search probes, so roughly log2(n) times per search — around 15 calls on a 27,000-element list. That is cheap for an attribute lookup or an index, and it is one reason the parameter is safe to reach for. It is not free for an expensive key: a key that parses a string or walks an object graph on every probe is worth precomputing into the stored element instead. Note also what `key=` does **not** change: `insort` still shifts the tail of the list on insert, so it remains O(n) in the list length no matter how cheap the key is. ### Ordering caveats bisect always assumes ascending order **of the keys**, and it validates nothing. If the list is sorted by one attribute and you pass a key extracting another, every answer is wrong with no error raised. There is no `reverse=` parameter either. For descending numeric data you can make the transformed sequence ascending with a negating key such as `lambda r: -r[1]`, remembering to negate the value you search for as well; for non-numeric descending data, storing the data ascending is far less error-prone than being clever. Finally, `key` is keyword-only, so it cannot be confused with `lo` and `hi` positionally — a small API detail that makes calls readable at a glance. ### Keeping the key honest The key function is part of the list's invariant, not a per-call detail: the sequence must already be ordered by the same key you search with, and every insertion must use it too. When that invariant lives as a lambda repeated at four call sites, one of them eventually diverges. Define the key once as a named module-level function and pass that everywhere, or wrap the list and its key in a small class so the ordering assumption has exactly one home. That is the difference between a searchable list and a list that happens to be sorted right now.

  • What error do you get if you pass a whole record as x to bisect_left with key= set?
    An immediate `TypeError` from the first comparison — the key function has reduced the element to, say, an int, and your tuple cannot be ordered against it. The failure is loud and happens on the very first probe rather than producing a wrong index, so the mistake never reaches production data. The mirror mistake, handing a bare key to insort, fails just as fast inside the key function.
  • How did you search a list of records by one field before Python 3.10?
    Either keep a parallel list of extracted keys, bisect that, and index the record list with the returned integer — every mutation then has to update both lists in step — or store the data as `(key, record)` tuples so ordinary tuple ordering compares the key first. The tuple form needs a tiebreaker between key and record, otherwise equal keys fall through to comparing the records themselves.
  • Does key= make insort any cheaper?
    No. It only changes what gets compared during the search, which was already the logarithmic part. The insert itself still shifts every element after the insertion point, so `insort` remains linear in the list length. If insert cost is your problem, a cheaper key will not help — you need a different structure or a batch-then-sort pattern.

saying these in an interview costs you the question

  • Passes a whole record as x to bisect_left with key=
  • Thinks key= makes insort logarithmic overall
  • Believes key= has always been in bisect
  • Says key= is applied to x in the search functions
  • Assumes key= can express descending order directly

context

resolving links…