bisect with Custom Keys

Concepts: pyBisectCustomKey, pySortedList

Python's bisect module works on values, not keys. If your sorted list contains tuples, objects, or anything where you want to binary search on a transformed value, you need to know the workarounds. Python 3.10 added a key parameter to bisect_left and bisect_right. For older versions, you have two options: extract a parallel list of keys, or use the SortedList from the sortedcontainers library. Both approaches come up in production code and occasionally in interviews. Python 3.10+: The key Parameter Pre-3.10: Parallel Key List Workaround The clean workaround for pre-3.10 Python is to maintain a separate sorted list of the keys you want to search on. This is the right approach in production: O(1) bisect on the key list, then index into the original list. SortedList from sortedcontainers For