Detailed Guide to Python bisect Module: Functions for Searching Sorted Lists

Python's bisect module provides a set of efficient functions based on binary search to locate insertion points or search for elements in already sorted lists, making it ideal for handling large ordered datasets.

The module offers O(log n) time complexity, which is significantly faster than linear search, and helps maintain list order when inserting new items.

Key functions include:

bisect_left(a, x, lo=0, hi=len(a)) – returns the leftmost insertion index for x in a .

bisect_right(a, x, lo=0, hi=len(a)) – returns the rightmost insertion index for x in a .

insort_left(a, x, lo=0, hi=len(a)) – inserts x into a at the leftmost suitable position.

insort_right(a, x, lo=0, hi=len(a)) – inserts x into a at the rightmost suitable position.

Example 1 – Find insertion position with bisect_left :

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 5
position = bisect.bisect_left(sorted_list, value)
print(f"The value {value} should be inserted at index {position}.")

Example 2 – Find insertion position with bisect_right :

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 5
position = bisect.bisect_right(sorted_list, value)
print(f"The value {value} should be inserted at index {position}.")

Example 3 – Insert element using insort_left :

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 5
bisect.insort_left(sorted_list, value)
print(f"List after inserting {value}: {sorted_list}")

Example 4 – Insert element using insort_right :

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 5
bisect.insort_right(sorted_list, value)
print(f"List after inserting {value}: {sorted_list}")

Example 5 – Locate an existing element:

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 7
position = bisect.bisect_left(sorted_list, value)
if position < len(sorted_list) and sorted_list[position] == value:
    print(f"The value {value} is at index {position}.")
else:
    print(f"The value {value} is not found.")

Example 6 – Handle duplicate elements:

import bisect
sorted_list = [1, 3, 4, 7, 7, 9, 11]
value = 7
left = bisect.bisect_left(sorted_list, value)
right = bisect.bisect_right(sorted_list, value)
print(f"The value {value} is found between indices {left} and {right - 1}.")

Example 7 – Find the nearest element to a target value:

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 6
pos = bisect.bisect_left(sorted_list, value)
if pos == 0:
    nearest = sorted_list[0]
elif pos == len(sorted_list):
    nearest = sorted_list[-1]
else:
    before = sorted_list[pos - 1]
    after = sorted_list[pos]
    nearest = before if value - before <= after - value else after
print(f"The value {value} is closest to {nearest}.")

Example 8 – Find the first element greater than or equal to a given value:

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 6
pos = bisect.bisect_left(sorted_list, value)
if pos < len(sorted_list):
    print(f"The first element >= {value} is {sorted_list[pos]}.")
else:
    print(f"No element >= {value} found.")

Example 9 – Find the last element less than or equal to a given value:

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
value = 6
pos = bisect.bisect_right(sorted_list, value) - 1
if pos >= 0:
    print(f"The last element <= {value} is {sorted_list[pos]}.")
else:
    print(f"No element <= {value} found.")

Example 10 – Retrieve a sub‑range between two values:

import bisect
sorted_list = [1, 3, 4, 7, 9, 11]
start = 4
end = 9
start_pos = bisect.bisect_left(sorted_list, start)
end_pos = bisect.bisect_right(sorted_list, end)
result = sorted_list[start_pos:end_pos]
print(f"Elements between {start} and {end}: {result}")