Python bisect: Efficient Sorted List Operations

import bisect
 
scores = [60, 70, 80, 90]
 
# Where would 75 go?
pos = bisect.bisect(scores, 75)
print(pos)  # 2 (between 70 and 80)
 
# Where would 80 go? (bisect_right = after existing 80s)
pos = bisect.bisect_right(scores, 80)
print(pos)  # 3
 
# bisect_left = before existing 80s
pos = bisect.bisect_left(scores, 80)
print(pos)  # 2

import bisect
 
scores = [60, 70, 80, 90]
 
bisect.insort(scores, 75)
print(scores)  # [60, 70, 75, 80, 90]
 
bisect.insort(scores, 85)
print(scores)  # [60, 70, 75, 80, 85, 90]

import bisect
 
data = [1, 2, 2, 2, 3]
 
# bisect_left: insert before existing
print(bisect.bisect_left(data, 2))   # 1
 
# bisect_right: insert after existing
print(bisect.bisect_right(data, 2))  # 4

import bisect
 
def binary_search(sorted_list, value):
    """Return index if found, -1 if not."""
    pos = bisect.bisect_left(sorted_list, value)
    if pos < len(sorted_list) and sorted_list[pos] == value:
        return pos
    return -1
 
data = [10, 20, 30, 40, 50]
print(binary_search(data, 30))  # 2
print(binary_search(data, 35))  # -1

import bisect
 
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    """Convert numeric score to letter grade."""
    i = bisect.bisect(breakpoints, score)
    return grades[i]
 
print(grade(55))   # F
print(grade(65))   # D
print(grade(75))   # C
print(grade(85))   # B
print(grade(95))   # A

import bisect
 
data = [10, 20, 30, 40, 50, 60, 70]
 
def find_in_range(sorted_list, low, high):
    """Find all values where low <= value <= high."""
    left = bisect.bisect_left(sorted_list, low)
    right = bisect.bisect_right(sorted_list, high)
    return sorted_list[left:right]
 
print(find_in_range(data, 25, 55))  # [30, 40, 50]

import bisect
 
def find_closest(sorted_list, target):
    """Find the closest value to target."""
    if not sorted_list:
        return None
    
    pos = bisect.bisect_left(sorted_list, target)
    
    if pos == 0:
        return sorted_list[0]
    if pos == len(sorted_list):
        return sorted_list[-1]
    
    before = sorted_list[pos - 1]
    after = sorted_list[pos]
    
    if after - target < target - before:
        return after
    return before
 
data = [10, 20, 30, 40, 50]
print(find_closest(data, 27))  # 30
print(find_closest(data, 23))  # 20

import bisect
 
# Sorted by second element
data = [(1, 10), (2, 20), (3, 30)]
keys = [item[1] for item in data]
 
# Find position for value 25
pos = bisect.bisect_left(keys, 25)
print(pos)  # 2 (would go between 20 and 30)

import bisect
 
class SortedList:
    def __init__(self):
        self._list = []
    
    def add(self, value):
        bisect.insort(self._list, value)
    
    def remove(self, value):
        pos = bisect.bisect_left(self._list, value)
        if pos < len(self._list) and self._list[pos] == value:
            self._list.pop(pos)
    
    def __contains__(self, value):
        pos = bisect.bisect_left(self._list, value)
        return pos < len(self._list) and self._list[pos] == value
    
    def __iter__(self):
        return iter(self._list)
 
sl = SortedList()
sl.add(3)
sl.add(1)
sl.add(2)
print(list(sl))  # [1, 2, 3]
print(2 in sl)   # True

import bisect
 
class Leaderboard:
    def __init__(self):
        self.scores = []
        self.names = []
    
    def add_score(self, name, score):
        # Insert maintaining sorted order (descending)
        # Use negative score for descending order
        pos = bisect.bisect_left(self.scores, -score)
        self.scores.insert(pos, -score)
        self.names.insert(pos, name)
    
    def top_n(self, n):
        return list(zip(self.names[:n], [-s for s in self.scores[:n]]))
 
board = Leaderboard()
board.add_score("Alice", 1500)
board.add_score("Bob", 1800)
board.add_score("Charlie", 1600)
 
print(board.top_n(2))  # [('Bob', 1800), ('Charlie', 1600)]

import bisect
import timeit
 
data = list(range(10000))
 
# Binary search: O(log n)
bisect_time = timeit.timeit(
    lambda: bisect.bisect(data, 5000),
    number=10000
)
 
# Linear search: O(n)
linear_time = timeit.timeit(
    lambda: data.index(5000) if 5000 in data else -1,
    number=10000
)
 
# bisect is ~100x faster on large lists