Python bisect Module: Binary Search and Sorted Lists

import bisect
 
scores = [60, 70, 80, 90]
 
# Where would 75 go?
pos = bisect.bisect(scores, 75)
print(pos)  # 2 (between 70 and 80)
 
# bisect_left vs bisect_right for duplicates
nums = [1, 3, 3, 3, 5]
print(bisect.bisect_left(nums, 3))   # 1 (before 3s)
print(bisect.bisect_right(nums, 3))  # 4 (after 3s)
print(bisect.bisect(nums, 3))        # 4 (same as bisect_right)

import bisect
 
scores = [60, 70, 80, 90]
 
# Insert 75 in sorted position
bisect.insort(scores, 75)
print(scores)  # [60, 70, 75, 80, 90]
 
# insort_left vs insort_right for duplicates
nums = [1, 3, 3, 3, 5]
bisect.insort_left(nums, 3)   # Insert before existing 3s
bisect.insort_right(nums, 3)  # Insert after existing 3s

import bisect
 
def binary_search(arr, x):
    """Find index of x in sorted array, or -1 if not found."""
    i = bisect.bisect_left(arr, x)
    if i < len(arr) and arr[i] == x:
        return i
    return -1
 
nums = [1, 3, 5, 7, 9]
print(binary_search(nums, 5))   # 2
print(binary_search(nums, 4))   # -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(85))   # B
print(grade(92))   # A
print(grade(55))   # F
print(grade(70))   # C

import bisect
 
# Sort by custom key
data = [('alice', 25), ('bob', 30), ('carol', 20)]
data.sort(key=lambda x: x[1])  # Sort by age
 
# Find where (name, 27) would go based on age
ages = [x[1] for x in data]  # [20, 25, 30]
pos = bisect.bisect(ages, 27)
print(pos)  # 2
 
# Python 3.10+ has key parameter
# pos = bisect.bisect(data, 27, key=lambda x: x[1])

import bisect
 
class Leaderboard:
    def __init__(self):
        self.scores = []
        self.names = []
    
    def add_score(self, name: str, score: int):
        # Find position (descending order)
        pos = bisect.bisect_left([-s for s in self.scores], -score)
        self.scores.insert(pos, score)
        self.names.insert(pos, name)
    
    def top_n(self, n: int):
        return list(zip(self.names[:n], self.scores[:n]))
 
board = Leaderboard()
board.add_score("Alice", 150)
board.add_score("Bob", 200)
board.add_score("Carol", 175)
print(board.top_n(3))
# [('Bob', 200), ('Carol', 175), ('Alice', 150)]

import bisect
 
def count_in_range(arr, lo, hi):
    """Count elements where lo <= x < hi."""
    return bisect.bisect_left(arr, hi) - bisect.bisect_left(arr, lo)
 
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(count_in_range(nums, 3, 7))  # 4 (3, 4, 5, 6)

import bisect
from datetime import datetime, timedelta
 
class TimeSeriesData:
    def __init__(self):
        self.timestamps = []
        self.values = []
    
    def add(self, timestamp: datetime, value):
        pos = bisect.bisect_left(self.timestamps, timestamp)
        self.timestamps.insert(pos, timestamp)
        self.values.insert(pos, value)
    
    def get_range(self, start: datetime, end: datetime):
        start_idx = bisect.bisect_left(self.timestamps, start)
        end_idx = bisect.bisect_right(self.timestamps, end)
        return list(zip(
            self.timestamps[start_idx:end_idx],
            self.values[start_idx:end_idx]
        ))

import bisect
 
# Find insertion point (right of duplicates)
bisect.bisect(a, x)
bisect.bisect_right(a, x)
 
# Find insertion point (left of duplicates)
bisect.bisect_left(a, x)
 
# Insert maintaining sort (right of duplicates)
bisect.insort(a, x)
bisect.insort_right(a, x)
 
# Insert maintaining sort (left of duplicates)
bisect.insort_left(a, x)