When are bisect_left and bisect_right not equal?

Understanding Python's bisect_left vs. bisect_right

Explore the subtle yet crucial differences between bisect_left and bisect_right in Python's bisect module, and learn when to use each for accurate insertion points in sorted sequences.

Python's bisect module provides efficient algorithms for inserting elements into a sorted list while maintaining its sorted order. The two primary functions, bisect_left and bisect_right (also aliased as bisect), are often used interchangeably, but they behave differently when encountering duplicate elements. Understanding this distinction is critical for correct data manipulation, especially in scenarios involving ranges, counts, or unique element handling.

The Core Difference: Handling Duplicates

Both bisect_left and bisect_right return an insertion point which keeps the list sorted. The key difference lies in how they treat elements equal to the one being searched for. Imagine you have a sorted list a and you're looking for an element x.

flowchart TD
    A[Start Search for X in Sorted List] --> B{Are there duplicates of X?}
    B -- Yes --> C{Is X found?}
    B -- No --> D[Insertion point is unique]
    C -- Yes --> E{`bisect_left`}
    C -- Yes --> F{`bisect_right`}
    E --> G["Returns insertion point *before* any existing X"]
    F --> H["Returns insertion point *after* any existing X"]
    G --> I[End]
    H --> I[End]
    D --> I[End]

Decision flow for bisect_left vs. bisect_right with duplicates.

bisect_left(a, x) returns an insertion point i such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. In simpler terms, if x is already present in the list, bisect_left will return the index of the first occurrence of x.

bisect_right(a, x) (or just bisect(a, x)) returns an insertion point i such that all e in a[:i] have e <= x, and all e in a[i:] have e > x. If x is already present, bisect_right will return the index after the last occurrence of x.

Practical Examples and Use Cases

Let's illustrate this with some Python code examples. Consider a sorted list with duplicate values.

import bisect

my_list = [10, 20, 20, 30, 40, 40, 40, 50]
value = 20

# Using bisect_left
index_left = bisect.bisect_left(my_list, value)
print(f"bisect_left for {value}: {index_left}")
# Expected output: bisect_left for 20: 1 (index of the first 20)

# Using bisect_right
index_right = bisect.bisect_right(my_list, value)
print(f"bisect_right for {value}: {index_right}")
# Expected output: bisect_right for 20: 3 (index after the last 20)

value_not_present = 25
index_left_np = bisect.bisect_left(my_list, value_not_present)
index_right_np = bisect.bisect_right(my_list, value_not_present)
print(f"bisect_left for {value_not_present}: {index_left_np}")
print(f"bisect_right for {value_not_present}: {index_right_np}")
# Expected output: Both will be 3, as 25 would be inserted between 20 and 30.

Demonstrating bisect_left and bisect_right with duplicate values.

Common Use Cases

Knowing when to use each function can simplify your code and prevent subtle bugs.

1. Counting Occurrences: To count how many times an element x appears in a sorted list a, you can use bisect_right(a, x) - bisect_left(a, x).

import bisect

my_list = [10, 20, 20, 30, 40, 40, 40, 50]
value_to_count = 40

count = bisect.bisect_right(my_list, value_to_count) - bisect.bisect_left(my_list, value_to_count)
print(f"The value {value_to_count} appears {count} times.")
# Expected output: The value 40 appears 3 times.

Counting occurrences of a value using bisect_left and bisect_right.

2. Finding a Range: To find all elements within a certain range [low, high] in a sorted list, you can use a[bisect_left(a, low) : bisect_right(a, high)].

import bisect

my_list = [10, 20, 20, 30, 40, 40, 40, 50]
low_bound = 20
high_bound = 40

start_index = bisect.bisect_left(my_list, low_bound)
end_index = bisect.bisect_right(my_list, high_bound)

range_elements = my_list[start_index:end_index]
print(f"Elements in range [{low_bound}, {high_bound}]: {range_elements}")
# Expected output: Elements in range [20, 40]: [20, 20, 30, 40, 40, 40]

Extracting a range of elements from a sorted list.

3. Maintaining Unique Elements: If you need to insert an element only if it's not already present, you might check bisect_left and then decide. If you want to ensure a new element is always inserted after existing duplicates, bisect_right is your choice.