bisect for Sorted-List Insertion
The `bisect` module is Python's binary-search-on-a-list primitive: `bisect_left` and `bisect_right` find the insertion index for a value in a sorted list in O(log n). This snippet covers the basic insertion-point query, the `insort` shortcut for keeping a list sorted as you build it, and the count-occurrences and rank-percentile recipes that fall out for free.
189 views
2
import bisect
sorted_nums = [1, 3, 4, 4, 4, 6, 9]
print(bisect.bisect_left(sorted_nums, 4)) # 2 (first index where 4 belongs)
print(bisect.bisect_right(sorted_nums, 4)) # 5 (one past the last 4)
print(bisect.bisect_left(sorted_nums, 5)) # 5 (would insert before 6)
print(bisect.bisect_left(sorted_nums, 0)) # 0 (insert at start)
print(bisect.bisect_left(sorted_nums, 99)) # 7 (insert at end)bisect_left(a, x) returns the leftmost index where x can be inserted to keep a sorted; bisect_right(a, x) returns one past the rightmost equal value. Both run in O(log n). The two together let you locate every occurrence of a value: bisect_right(a, x) - bisect_left(a, x) is the count. Note that bisect does NOT verify the list is sorted; passing an unsorted list silently returns garbage, which is a class of bug worth knowing about.
import bisect
sorted_list = []
for x in [5, 1, 3, 8, 2, 7, 4]:
bisect.insort(sorted_list, x)
print(sorted_list) # [1, 2, 3, 4, 5, 7, 8]
# Streaming median tracker (toy example)
stream = [4, 1, 7, 9, 2, 5, 3]
seen = []
for x in stream:
bisect.insort(seen, x)
mid = len(seen) // 2
median = seen[mid] if len(seen) % 2 == 1 else (seen[mid - 1] + seen[mid]) / 2
print(f'after {x:>2}: median={median}')bisect.insort(list, x) inserts x at the correct position to keep the list sorted, in O(log n) for the search but O(n) for the actual insertion (because Python lists must shift the tail). For very large lists, this is slower than appending and sorting once at the end; for small to medium lists or streaming inputs that need a running query, it is the right tool. The streaming-median example shows how to maintain a sorted view of an unbounded input without re-sorting on every read.
import bisect
ages = sorted([22, 25, 25, 30, 35, 40, 40, 40, 50])
# How many people are exactly 40?
count_40 = bisect.bisect_right(ages, 40) - bisect.bisect_left(ages, 40)
print(count_40) # 3
# How many are strictly younger than 40?
younger = bisect.bisect_left(ages, 40)
print(younger) # 5
# What percentile is age 30?
rank = bisect.bisect_left(ages, 30)
percentile = round(100 * rank / len(ages), 1)
print(percentile) # 33.3 (33% of values are strictly less than 30)Once you have a sorted array, bisect answers a whole family of queries in O(log n): exact count, less-than count, between-A-and-B count, percentile rank. Pre-sort once, then answer each query in log time, which beats a linear scan when the same data is queried many times. For rank-and-quantile work over fixed datasets, this is the simplest pure-Python approach; for unbounded streams, look at sorted-container third-party libraries that maintain log-time inserts.