Python bisect: Binary Search for Sorted Sequences

import bisect
 
sorted_list = [1, 3, 5, 7, 9]
 
# Where would 4 go?
pos = bisect.bisect(sorted_list, 4)
print(pos)  # 2 (between 3 and 5)
 
# bisect_left vs bisect_right for duplicates
nums = [1, 3, 3, 3, 5]
 
print(bisect.bisect_left(nums, 3))   # 1 (before first 3)
print(bisect.bisect_right(nums, 3))  # 4 (after last 3)
print(bisect.bisect(nums, 3))        # 4 (bisect = bisect_right)

import bisect
 
sorted_list = [1, 3, 5, 7]
 
# Insert in correct position
bisect.insort(sorted_list, 4)
print(sorted_list)  # [1, 3, 4, 5, 7]
 
bisect.insort(sorted_list, 3)  # Duplicate
print(sorted_list)  # [1, 3, 3, 4, 5, 7]
 
# insort_left for before duplicates
nums = [1, 3, 5]
bisect.insort_left(nums, 3)
print(nums)  # [1, 3, 3, 5]

import bisect
 
def binary_search(sorted_list: list, target) -> int:
    """Return index of target, or -1 if not found."""
    i = bisect.bisect_left(sorted_list, target)
    if i != len(sorted_list) and sorted_list[i] == target:
        return i
    return -1
 
nums = [1, 2, 3, 5, 8, 13, 21]
print(binary_search(nums, 5))   # 3
print(binary_search(nums, 4))   # -1
print(binary_search(nums, 21))  # 6

import bisect
 
def find_range(sorted_list: list, lo, hi) -> list:
    """Find all elements where lo <= x < hi."""
    left = bisect.bisect_left(sorted_list, lo)
    right = bisect.bisect_left(sorted_list, hi)
    return sorted_list[left:right]
 
nums = [1, 3, 5, 7, 9, 11, 13, 15]
 
print(find_range(nums, 5, 12))   # [5, 7, 9, 11]
print(find_range(nums, 0, 5))    # [1, 3]
print(find_range(nums, 10, 20))  # [11, 13, 15]

import bisect
 
def count_occurrences(sorted_list: list, value) -> int:
    """Count occurrences of value in sorted list."""
    left = bisect.bisect_left(sorted_list, value)
    right = bisect.bisect_right(sorted_list, value)
    return right - left
 
nums = [1, 2, 2, 2, 3, 3, 4, 5]
print(count_occurrences(nums, 2))  # 3
print(count_occurrences(nums, 3))  # 2
print(count_occurrences(nums, 6))  # 0

import bisect
 
def floor(sorted_list: list, value):
    """Largest element <= value, or None."""
    i = bisect.bisect_right(sorted_list, value) - 1
    return sorted_list[i] if i >= 0 else None
 
def ceiling(sorted_list: list, value):
    """Smallest element >= value, or None."""
    i = bisect.bisect_left(sorted_list, value)
    return sorted_list[i] if i < len(sorted_list) else None
 
nums = [1, 3, 5, 7, 9]
 
print(floor(nums, 6))    # 5
print(ceiling(nums, 6))  # 7
print(floor(nums, 0))    # None
print(ceiling(nums, 10)) # None

import bisect
 
class SortedList:
    """Sorted list with binary search operations."""
    
    def __init__(self, iterable=None):
        self._list = sorted(iterable) if iterable else []
    
    def add(self, value):
        bisect.insort(self._list, value)
    
    def remove(self, value):
        i = bisect.bisect_left(self._list, value)
        if i < len(self._list) and self._list[i] == value:
            del self._list[i]
        else:
            raise ValueError(f"{value} not found")
    
    def __contains__(self, value):
        i = bisect.bisect_left(self._list, value)
        return i < len(self._list) and self._list[i] == value
    
    def __iter__(self):
        return iter(self._list)
    
    def __len__(self):
        return len(self._list)
 
# Usage
sl = SortedList([3, 1, 4, 1, 5])
print(list(sl))  # [1, 1, 3, 4, 5]
 
sl.add(2)
print(3 in sl)   # True

import bisect
 
def grade(score: float) -> str:
    """Convert score to letter grade."""
    breakpoints = [60, 70, 80, 90]
    grades = ['F', 'D', 'C', 'B', 'A']
    
    i = bisect.bisect(breakpoints, score)
    return grades[i]
 
print(grade(85))  # B
print(grade(92))  # A
print(grade(55))  # F
print(grade(70))  # C (exactly 70)

import bisect
from typing import Any, Tuple
 
class PriorityQueue:
    """Simple priority queue using sorted list."""
    
    def __init__(self):
        self._items: list[Tuple[int, Any]] = []
    
    def push(self, priority: int, item: Any):
        bisect.insort(self._items, (priority, item))
    
    def pop(self) -> Tuple[int, Any]:
        return self._items.pop(0)  # Lowest priority first
    
    def __len__(self):
        return len(self._items)
 
pq = PriorityQueue()
pq.push(3, "medium")
pq.push(1, "high")
pq.push(5, "low")
 
print(pq.pop())  # (1, 'high')
print(pq.pop())  # (3, 'medium')

import bisect
 
# Sort by second element
data = [(1, 'a'), (3, 'c'), (5, 'e')]
 
# Find position for (4, 'd') based on first element
pos = bisect.bisect(data, (4, 'd'))  # Works with tuples
 
# Or use key parameter (Python 3.10+)
pos = bisect.bisect(data, 4, key=lambda x: x[0])

import bisect
 
class KeyWrapper:
    """Wrap values to enable custom comparison."""
    
    def __init__(self, value, key):
        self.value = value
        self.key = key(value)
    
    def __lt__(self, other):
        return self.key < other.key
 
def bisect_with_key(sorted_list, value, key):
    """Binary search with custom key function."""
    wrapped = [KeyWrapper(x, key) for x in sorted_list]
    target = KeyWrapper(value, key)
    return bisect.bisect_left(wrapped, target)
 
# Sort strings by length
words = ['a', 'bb', 'ccc', 'dddd', 'eeeee']
pos = bisect_with_key(words, 'xx', key=len)
print(pos)  # 1 (length 2 goes after 'a')

import bisect
 
def nearest(sorted_list: list, value):
    """Find nearest value in sorted list."""
    if not sorted_list:
        return None
    
    pos = bisect.bisect_left(sorted_list, value)
    
    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]
    
    return before if value - before <= after - value else after
 
nums = [1, 3, 8, 10, 15]
print(nearest(nums, 6))   # 8
print(nearest(nums, 5))   # 3
print(nearest(nums, 12))  # 10