Bisect Right

Introduction

Bisect Right is a binary search function used to locate the rightmost insertion point for a given value in a sorted list. It ensures that if duplicates exist, the new element will be inserted after the existing entries, preserving the order.

It is a part of Python’s built-in bisect module and is frequently used for maintaining sorted sequences, implementing upper bound searches, and solving problems in competitive programming, databases, and data science.

What Is Bisect Right?

bisect_right(a, x) returns the index at which x should be inserted into the list a so that the order is preserved and the new element goes to the right of any existing entries equal to x.

It answers the question:

“Where is the rightmost index at which I can insert x into a and keep it sorted?”

Syntax

import bisect

bisect.bisect_right(a, x, lo=0, hi=len(a))

Parameters:

a: The sorted list.
x: The value to insert.
lo: Lower bound for search (inclusive). Default is 0.
hi: Upper bound for search (exclusive). Default is len(a).

Returns:

An integer representing the rightmost insertion point.

Example: Basic Usage

import bisect

data = [10, 20, 20, 20, 30]
index = bisect.bisect_right(data, 20)
print(index)  # Output: 4

Since 20 appears three times, bisect_right returns 4, the index after the last 20.

Visual Illustration

Given this list:

a = [10, 20, 20, 20, 30]

bisect_left(a, 20) → returns 1 (first 20)
bisect_right(a, 20) → returns 4 (after last 20)

Difference Between bisect_right and bisect_left

Feature	`bisect_left`	`bisect_right`
Insertion Point	Before existing items	After existing items
Lower Bound Search	Yes	No
Upper Bound Search	No	Yes
Handles duplicates	Returns first match	Returns after last match

Custom Implementation

Understanding the internal binary search logic gives insight into how bisect_right works:

def bisect_right_manual(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

Note: Only the comparison sign differs from bisect_left.

Use Case: Count Elements ≤ x

To count how many elements in a sorted list are less than or equal to x:

count = bisect.bisect_right(a, x)

This is highly useful in range queries, cumulative frequency tables, and prefix sums.

Practical Example: Insert While Maintaining Order

from bisect import bisect_right

def insert_sorted_right(a, x):
    i = bisect_right(a, x)
    a.insert(i, x)

arr = [1, 2, 2, 3]
insert_sorted_right(arr, 2)
print(arr)  # Output: [1, 2, 2, 2, 3]

This inserts the value after all existing 2s, preserving sorted order.

Working with Custom Data

To use bisect_right with complex structures like objects or tuples, separate the sorting key into a secondary list:

from bisect import bisect_right

items = [(1, 'A'), (2, 'B'), (2, 'C'), (3, 'D')]
keys = [x[0] for x in items]

i = bisect_right(keys, 2)
print(i)  # Output: 3

This identifies the insertion point after all items with key 2.

Counting Occurrences Using bisect_right

To count how many times a value x occurs in a sorted list a:

from bisect import bisect_left, bisect_right

def count_occurrences(a, x):
    return bisect_right(a, x) - bisect_left(a, x)

Example:

a = [5, 10, 10, 10, 15, 20]
print(count_occurrences(a, 10))  # Output: 3

Range Query Example

To count how many values in a sorted list are within the range [low, high]:

def count_range(a, low, high):
    return bisect_right(a, high) - bisect_left(a, low)

Performance

Time Complexity: O(log n)
Space Complexity: O(1)

Because it uses binary search, bisect_right is extremely fast even on large datasets.

Comparison with Other Search Approaches

Method	Speed	Sorted Input Required	Use Case
`linear search`	O(n)	No	Unsorted lists
`bisect_right`	O(log n)	Yes	Sorted lists, duplicates
`index()`	O(n)	No	Finds exact match
`set` lookup	O(1) avg	No	Fast presence test, no order

Common Mistakes

Using on unsorted lists — always ensure the list is sorted.
Forgetting the difference between left and right — choose based on whether you want the first or last match.
Not adjusting bounds (lo, hi) — may cause incorrect indexing.

Real-World Applications

Domain	Application Example
Finance	Sorted time series insertion and analysis
Search Engines	Inverted index maintenance
Gaming	Score leaderboard ranking
Machine Learning	Threshold-based bucketing
Competitive Coding	Frequency counting, lower/upper bounds

Using bisect.insort_right

insort_right is the counterpart that not only finds the index but also inserts the element:

from bisect import insort_right

a = [10, 20, 30]
insort_right(a, 20)
print(a)  # Output: [10, 20, 20, 30]

Summary

bisect_right is a powerful and efficient tool for handling sorted lists, particularly when working with duplicates and maintaining ordered data. It returns the index at which to insert an element so that the new element goes after any existing entries of the same value.

By using bisect_right, you gain: