Python’s bisect module provides binary search on sorted lists. import bisect. bisect_left: bisect.bisect_left(a, x) → index where x would be inserted to keep a sorted; if x present, index of leftmost x. bisect_right: bisect.bisect_right(a, x) (alias bisect.bisect) → index after rightmost x. insort_left: bisect.insort_left(a, x) — insert x maintaining sort. insort_right: bisect.insort_right(a, x) (alias bisect.insort). key: bisect.bisect_left(a, x, key=fn) (Python 3.10+) — compare via key(a[i]) vs x. Search pattern: i = bisect_left(a, x); a[i] == x → found. Range count: bisect_right(a, hi) - bisect_left(a, lo). Nearest: a[min(bisect_left(a,x), len(a)-1)]. Step function: grades = [60,70,80,90]; letters = “FDCBA”; letters[bisect_right(grades, score)]. insort is O(n) due to list insert; bisect_left/right is O(log n). Works on any sorted sequence supporting __len__ and __getitem__. Claude Code generates rate-table lookups, range queries, sorted-insert pipelines, and scheduling event finders.
CLAUDE.md for bisect
## bisect Stack
- Stdlib: import bisect
- Find: i = bisect.bisect_left(sorted_list, value) — O(log n)
- Exact: if i < len(a) and a[i] == value: found
- Range: count = bisect.bisect_right(a, hi) - bisect.bisect_left(a, lo)
- Insert: bisect.insort(a, value) — O(n) due to list shift
- Key: bisect.bisect_left(a, x, key=lambda e: e.score) — Python 3.10+bisect Binary Search Pipeline
# app/searchutil.py — binary search, range queries, step tables, nearest
from __future__ import annotations
import bisect
from dataclasses import dataclass
from typing import Any, Callable, Sequence, TypeVar
T = TypeVar("T")
K = TypeVar("K")
# ─────────────────────────────────────────────────────────────────────────────
# 1. Binary search helpers
# ─────────────────────────────────────────────────────────────────────────────
def search(sorted_list: list, value: Any) -> int | None:
"""
Return index of value in sorted_list, or None if not found.
Example:
search([1, 3, 5, 7, 9], 5) # 2
search([1, 3, 5, 7, 9], 4) # None
"""
i = bisect.bisect_left(sorted_list, value)
if i < len(sorted_list) and sorted_list[i] == value:
return i
return None
def contains(sorted_list: list, value: Any) -> bool:
"""
Return True if value is in sorted_list using binary search.
Example:
contains([1, 3, 5, 7, 9], 5) # True
contains([1, 3, 5, 7, 9], 4) # False
"""
i = bisect.bisect_left(sorted_list, value)
return i < len(sorted_list) and sorted_list[i] == value
def insertion_point(sorted_list: list, value: Any, side: str = "left") -> int:
"""
Return the index where value should be inserted to maintain sort order.
side="left" puts value before any existing equal values; "right" puts after.
Example:
insertion_point([1, 3, 3, 5], 3, "left") # 1
insertion_point([1, 3, 3, 5], 3, "right") # 3
"""
if side == "left":
return bisect.bisect_left(sorted_list, value)
return bisect.bisect_right(sorted_list, value)
# ─────────────────────────────────────────────────────────────────────────────
# 2. Range queries
# ─────────────────────────────────────────────────────────────────────────────
def count_in_range(
sorted_list: list,
lo: Any,
hi: Any,
inclusive: tuple[bool, bool] = (True, True),
) -> int:
"""
Count elements in sorted_list within [lo, hi].
Example:
count_in_range([1,2,3,4,5,6,7,8,9,10], 3, 7) # 5
count_in_range([1,2,2,3,3,3,4], 2, 3) # 5
"""
lo_fn = bisect.bisect_left if inclusive[0] else bisect.bisect_right
hi_fn = bisect.bisect_right if inclusive[1] else bisect.bisect_left
return hi_fn(sorted_list, hi) - lo_fn(sorted_list, lo)
def slice_range(
sorted_list: list,
lo: Any,
hi: Any,
inclusive: tuple[bool, bool] = (True, True),
) -> list:
"""
Return elements in sorted_list within [lo, hi].
Example:
slice_range([1,2,3,4,5,6,7], 3, 5) # [3, 4, 5]
"""
lo_fn = bisect.bisect_left if inclusive[0] else bisect.bisect_right
hi_fn = bisect.bisect_right if inclusive[1] else bisect.bisect_left
return sorted_list[lo_fn(sorted_list, lo): hi_fn(sorted_list, hi)]
def nearest(sorted_list: list[float], value: float) -> float:
"""
Return the element in sorted_list closest to value.
Example:
nearest([1.0, 3.0, 6.0, 10.0], 4.0) # 3.0
nearest([1.0, 3.0, 6.0, 10.0], 5.0) # 6.0
"""
if not sorted_list:
raise ValueError("Empty list")
i = bisect.bisect_left(sorted_list, value)
candidates = []
if i < len(sorted_list):
candidates.append(sorted_list[i])
if i > 0:
candidates.append(sorted_list[i - 1])
return min(candidates, key=lambda x: abs(x - value))
def floor_value(sorted_list: list, value: Any) -> Any | None:
"""
Return the largest element ≤ value, or None if all elements > value.
Example:
floor_value([1, 3, 5, 7, 9], 6) # 5
floor_value([1, 3, 5, 7, 9], 0) # None
"""
i = bisect.bisect_right(sorted_list, value)
return sorted_list[i - 1] if i > 0 else None
def ceiling_value(sorted_list: list, value: Any) -> Any | None:
"""
Return the smallest element ≥ value, or None if all elements < value.
Example:
ceiling_value([1, 3, 5, 7, 9], 4) # 5
ceiling_value([1, 3, 5, 7, 9], 9) # 9
ceiling_value([1, 3, 5, 7, 9], 10) # None
"""
i = bisect.bisect_left(sorted_list, value)
return sorted_list[i] if i < len(sorted_list) else None
# ─────────────────────────────────────────────────────────────────────────────
# 3. Step-function / lookup tables
# ─────────────────────────────────────────────────────────────────────────────
def step_lookup(
breakpoints: list,
values: list,
query: Any,
) -> Any:
"""
Step-function lookup: return values[i] where breakpoints[i-1] <= query < breakpoints[i].
len(values) must be len(breakpoints) + 1.
Example:
# Grade buckets: <60=F, <70=D, <80=C, <90=B, >=90=A
grade = step_lookup([60, 70, 80, 90], ["F","D","C","B","A"], 83) # "B"
"""
if len(values) != len(breakpoints) + 1:
raise ValueError("len(values) must be len(breakpoints)+1")
i = bisect.bisect_right(breakpoints, query)
return values[i]
def rate_table_lookup(
thresholds: list[float],
rates: list[float],
amount: float,
) -> float:
"""
Look up a tiered rate for amount.
Example:
# Shipping: $0–$25: $5.99, $25–$50: $4.99, $50+: free
rate = rate_table_lookup([25.0, 50.0], [5.99, 4.99, 0.0], 35.0) # 4.99
"""
return step_lookup(thresholds, rates, amount)
# ─────────────────────────────────────────────────────────────────────────────
# 4. Sorted list maintenance
# ─────────────────────────────────────────────────────────────────────────────
class SortedInsertList(list):
"""
A list that maintains sorted order on insort() calls.
Subclasses list for full compatibility.
Example:
sl = SortedInsertList()
sl.insort(5)
sl.insort(2)
sl.insort(8)
print(sl) # [2, 5, 8]
"""
def insort(self, value: Any, side: str = "right") -> None:
"""Insert value maintaining sorted order. O(n) due to list shift."""
if side == "left":
bisect.insort_left(self, value)
else:
bisect.insort_right(self, value)
def search(self, value: Any) -> int | None:
return search(self, value)
def slice_range(self, lo: Any, hi: Any) -> list:
return slice_range(self, lo, hi)
def count_range(self, lo: Any, hi: Any) -> int:
return count_in_range(self, lo, hi)
# ─────────────────────────────────────────────────────────────────────────────
# 5. Key-based binary search (Python 3.10+ native, fallback for older)
# ─────────────────────────────────────────────────────────────────────────────
@dataclass(order=True)
class SortedItem:
"""Wrapper to enable bisect with a sort key on arbitrary objects."""
key: Any
value: Any = None
def search_by_key(
sorted_items: list[Any],
key_fn: Callable[[Any], Any],
target_key: Any,
) -> int | None:
"""
Binary search on a list sorted by key_fn(item).
Returns index of first match or None.
Example:
events = sorted(events, key=lambda e: e.timestamp)
idx = search_by_key(events, lambda e: e.timestamp, target_ts)
"""
keys = [SortedItem(key=key_fn(item)) for item in sorted_items]
target = SortedItem(key=target_key)
i = bisect.bisect_left(keys, target)
if i < len(sorted_items) and key_fn(sorted_items[i]) == target_key:
return i
return None
def count_by_key_range(
sorted_items: list[Any],
key_fn: Callable[[Any], Any],
lo_key: Any,
hi_key: Any,
) -> int:
"""
Count items where lo_key <= key_fn(item) <= hi_key.
Example:
# Count events between two timestamps
count = count_by_key_range(events, lambda e: e.ts, start_ts, end_ts)
"""
keys = [SortedItem(key_fn(item)) for item in sorted_items]
lo_idx = bisect.bisect_left(keys, SortedItem(lo_key))
hi_idx = bisect.bisect_right(keys, SortedItem(hi_key))
return hi_idx - lo_idx
# ─────────────────────────────────────────────────────────────────────────────
# Demo
# ─────────────────────────────────────────────────────────────────────────────
if __name__ == "__main__":
print("=== bisect demo ===")
a = [1, 3, 3, 5, 7, 9, 11]
print("\n--- search / contains ---")
print(f" search(a, 5): {search(a, 5)}")
print(f" search(a, 4): {search(a, 4)}")
print(f" contains(a, 3): {contains(a, 3)}")
print(f" contains(a, 4): {contains(a, 4)}")
print("\n--- insertion_point ---")
print(f" bisect_left(a, 3): {insertion_point(a, 3, 'left')}")
print(f" bisect_right(a, 3): {insertion_point(a, 3, 'right')}")
print("\n--- count_in_range / slice_range ---")
nums = list(range(1, 21))
print(f" count [5, 15]: {count_in_range(nums, 5, 15)}")
print(f" slice [5, 10]: {slice_range(nums, 5, 10)}")
print(f" count (5, 15) exclusive hi: {count_in_range(nums, 5, 15, (True, False))}")
print("\n--- nearest / floor / ceiling ---")
vals = [1.0, 3.0, 6.0, 10.0]
for q in [0.5, 2.0, 4.5, 7.0, 12.0]:
print(f" q={q:5.1f} nearest={nearest(vals, q)!r:5} "
f"floor={floor_value(vals, q)!r:5} ceiling={ceiling_value(vals, q)!r}")
print("\n--- step_lookup (grades) ---")
breakpoints = [60, 70, 80, 90]
labels = ["F", "D", "C", "B", "A"]
for score in [55, 62, 75, 83, 91]:
grade = step_lookup(breakpoints, labels, score)
print(f" score={score} grade={grade}")
print("\n--- rate_table_lookup (shipping) ---")
for amount in [10.0, 30.0, 60.0]:
rate = rate_table_lookup([25.0, 50.0], [5.99, 4.99, 0.0], amount)
print(f" ${amount:.2f} → shipping ${rate:.2f}")
print("\n--- SortedInsertList ---")
sl = SortedInsertList()
for v in [5, 2, 8, 1, 9, 3]:
sl.insort(v)
print(f" sorted: {list(sl)}")
print(f" range [2,6]: {sl.slice_range(2, 6)}")
print(f" count [2,8]: {sl.count_range(2, 8)}")
print("\n=== done ===")For the sortedcontainers.SortedList alternative — sortedcontainers.SortedList (PyPI) wraps a sorted list with O(log n) insertions AND O(log n) deletions using a clever B-tree-like internal structure, while exposing all standard list operations; stdlib bisect.insort is O(n) for insertion due to list shifting — use SortedList when insertion throughput matters (many writes into a maintained sorted collection), stdlib bisect for read-heavy lookup patterns where the data is written once and queried many times (rate tables, grade buckets, static event schedules). For the numpy.searchsorted alternative — numpy.searchsorted(a, v) performs the same binary search on NumPy arrays with vectorized batch queries: np.searchsorted(sorted_array, [val1, val2, val3]) returns three indices in one call; stdlib bisect operates on Python lists and handles one query at a time — use numpy.searchsorted for batch lookups over large numerical arrays in data science pipelines, stdlib bisect for Python-native sorted lists, custom comparison logic, and zero-dependency environments. The Claude Skills 360 bundle includes bisect skill sets covering search()/contains()/insertion_point() search helpers, count_in_range()/slice_range()/nearest()/floor_value()/ceiling_value() range query utilities, step_lookup()/rate_table_lookup() step-function tables, SortedInsertList maintained-sort list subclass, and search_by_key()/count_by_key_range() key-based binary search. Start with the free tier to try binary search patterns and bisect algorithm code generation.