Binary search is an algorithm that repeatedly halves an ordered search interval to locate a value or a boundary. For quant work, the boundary is often the useful answer: the first available maturity at or beyond a requested horizon, or the last recorded timestamp no later than a valuation time.
The ordering makes the elimination safe. If a middle maturity is too short, every earlier maturity is too short as well. Without that ordering, discarding half the candidates has no justification.
Find the boundary, then ask the financial question
Suppose a fictional maturity grid, in days, is
[30, 90, 180, 365]. We want the first maturity at least 100 days. A lower bound is the first position whose value is greater than or equal to the target, or the position just after the final element if no such value exists.Using zero-based indices, the lower bound is index 2, containing 180 days. The 100-day target is absent. Choosing 180 days satisfies the stated lookup rule; it does not price a 100-day claim, interpolate a curve, or select the nearest maturity. That financial rule must be decided separately.
![Fictional sorted maturity days [30, 90, 180, 365] have zero-based indices 0 to 3. For target 100 days, inspect index 2 with value 180, then index 1 with value 90. The remaining insertion index is 2: 180 is the first maturity at least 100 days, but 100 is absent. Target 90 returns index 1; target 400 returns end index 4; an empty list returns 0.](https://dn03ejzfqody8.cloudfront.net/assets/glossary/binary-search/lower-bound.svg)
A lower-bound search finds the boundary between maturities below 100 days and those at least 100 days. The insertion index can identify a successor without establishing exact membership. All maturities are fictional; indices start at zero.
The trace starts with the half-open interval
[lo, hi) = [0, 4): lo is included, hi is excluded. Its middle index is 2. Since 180 is at least 100, the first qualifying position cannot be to its right; set hi = 2. The next middle index is 1. Since 90 is below 100, set lo = 2. Now both boundaries equal 2, so the search stops. The lower-bound position always remains between the boundaries, including the upper endpoint.This halves the candidate interval rather than checking every element. On a random-access array, with constant-cost indexing and comparisons, its time complexity is for a nonempty sequence of length . A linked structure that must traverse nodes to reach each midpoint does not inherit that time bound merely by using the same comparisons. Sorting an initially unordered collection also has a cost, separate from the search.
Python: insertion is not membership
Python's
bisect_left returns the lower-bound insertion index. Guard the end position before reading the element, then compare for equality if exact membership matters.from bisect import bisect_left
tenors = [30, 90, 180, 365] # Fictional days; sorted ascending.
for target in [100, 90, 400]:
i = bisect_left(tenors, target)
candidate = tenors[i] if i < len(tenors) else None
exact = i < len(tenors) and tenors[i] == target
print(target, i, candidate, exact)
# 100 2 180 False
# 90 1 90 True
# 400 4 None False
print(bisect_left([], 100))
# 0An insertion index equal to the length is valid, but it is not an element index: for target 400 the index is 4 and there is no successor. An empty list similarly returns 0 without containing a value.
bisect_left only searches; it does not insert or mutate the list. Python's official contract specifies the insertion boundary; the equality check above supplies the membership test.Keep the search contract intact
- Same order, same key. Sort ascending by the field being searched. If records are ordered by maturity days, search maturity days rather than price or a display string. With Python's
key=argument, pass the target already in key space: the search applies the key function to stored records, not to the target. This argument is available from Python 3.10. - Choose a duplicate policy. For
[30, 90, 90, 180], searching for 90 gives index 1 withbisect_leftand index 3 withbisect_right. Left means before equal entries; right means after them. For a latest-timestamp-at-or-before query, the predecessor of the right insertion point implements the boundary rule, provided the insertion point is greater than zero. Equal timestamps still need a policy for choosing among records. - Use coherent comparisons. Missing or unordered keys, including floating-point NaN, need explicit handling before the search. A sequence containing them does not supply the ordinary ordered partition assumed here. Exact membership is equality of stored values, not a tolerance-based financial match.
- Maintain the sequence. Keep it sorted and stable while searching; concurrent mutation invalidates the guarantee. Finding a position is logarithmic under the assumptions above, but inserting into a Python list can shift a linear number of elements.
insorttherefore has worst-case insertion cost. The performance notes make this distinction explicit.
For the broader choice between sorted lists and ordered structures, the built-in ADTs lesson develops the search-versus-insertion trade-off in its
bisect section. The public page is a preview; the full lesson requires membership.Sources
- Python 3.14 bisect documentation: insertion contracts, equality checks, keys and performance. Documentation read as version 3.14.10; the example was executed with Python 3.14.4.
- CPython 3.14 reference implementation: midpoint updates and half-open search intervals. CPython can replace these reference functions with its C implementation.