Skip to content
Hari KharelStudy

Sorted containers and bisect

intermediateCommon atGoogleStripeJane StreetAnthropicTwo SigmaRead firstBinary searchBinary search treesPractise in the Sandbox →

A sorted container keeps values in order so you can ask “where would x go?” in O(log n). On a sorted list, bisect_left(a, x) is the first index whose value is ≥ x, and bisect_right(a, x) is the first index whose value is > x; they differ only when x is present, and their difference is how many copies of x there are. Inserting into a plain sorted list is O(n) because of shifting; a balanced tree (C# SortedSet, SortedDictionary) or Python’s third-party SortedList makes it O(log n). TypeScript has none built in.

The idea in plain words

Section titled “The idea in plain words”

Picture a bookshelf sorted by height. Someone hands you a new book. Finding its spot is quick: look in the middle, then the middle of the correct half, and so on. That’s binary search, O(log n) looks.

Making room is the slow part. Every book to the right of the spot has to slide over by one. On a shelf of a million books that’s up to a million slides. That’s a sorted array: fast to search, slow to change.

There are two kinds of question you’ll ask of the shelf:

  • Positions: “where would x go?”, “how many are smaller than x?”, “which is the first one at least x?” Binary search answers all of these, and the precise answer depends on what happens with ties.
  • Changes: “add x”, “remove x”. On an array these cost O(n). If there are many of them, use a structure that doesn’t shift: a balanced tree, or a list of small sorted chunks.

See it

Section titled “See it”

Run bisect_left and bisect_right for the same x and watch where lo and hi meet. With x = 3 they land on either side of the run of 3s. With x = 4 (absent) they land on the same slot. Then try insort and count the shifts.

bisect_left vs bisect_right, step by step
interactive
 
run
1
3
3
3
5
8
9
12
·
012345678
n8
x3
midequal to xruled outinsertion slotshiftedinserted
A sorted list with three 3s. bisect_left and bisect_right only disagree when x is present; try x = 3, then x = 4.
1 / 1
Operation log
Run bisect_left(3) and bisect_right(3): their difference is how many 3s there are.

Things to try:

  • bisect_left(3) returns 1 and bisect_right(3) returns 4. The 3s are exactly a[1:4], and there are 4 − 1 = 3 of them.
  • x = 0 returns 0 and x = 99 returns 8 (= n). “Before everything” and “after everything” are both valid answers, which is why hi starts at n, not n − 1.
  • insort(2) near the front: the shift count is almost n.

When to reach for it

Section titled “When to reach for it”
The problem says… Why a sorted container fits
“how many values are less than / at most x?” That count is bisect_left / bisect_right.
“the closest value to x”, “next bigger”, “previous smaller” The neighbors of the insertion point.
“all values between lo and hi” One bisect for each end, then a slice: O(log n + k).
“keep it sorted as values arrive and leave” A tree-backed set or SortedList keeps every change O(log n).
“the k-th smallest of a changing collection” SortedList[k] is O(log n); a heap can’t index.
static data, many lookups Sort once (O(n log n)), then bisect forever. No container needed.

How it works

Section titled “How it works”

The two searches

Section titled “The two searches”
  1. Set lo = 0, hi = n. The answer is always somewhere in [lo, hi], including n for “after everything”.
  2. Look at mid = (lo + hi) // 2. For bisect_left, if a[mid] < x the answer is right of mid (lo = mid + 1); otherwise mid might be it (hi = mid). For bisect_right, use a[mid] <= x instead.
  3. Stop when lo == hi. That’s the insertion point. The loop never reads a[n], so it never goes out of bounds.
bisect_impl.py
import bisect




def lower_bound(a: list[int], x: int) -> int:
    """bisect_left: first index i with a[i] >= x (len(a) if none)."""
    lo, hi = 0, len(a)            # 1. answer is in [lo, hi]; hi = len(a) means "at the end"
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:            # 2. mid is too small: the answer is strictly right of it
            lo = mid + 1
        else:                     #    mid might be the answer: keep it in range
            hi = mid
    return lo                     # 3. lo == hi: the insertion point




def upper_bound(a: list[int], x: int) -> int:
    """bisect_right: first index i with a[i] > x. The only change is < becomes <=."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo




if __name__ == "__main__":
    a = [1, 3, 3, 3, 5, 8]
    assert (lower_bound(a, 3), upper_bound(a, 3)) == (1, 4)  # the 3s live in a[1:4]
    assert upper_bound(a, 3) - lower_bound(a, 3) == 3        # count of 3s
    assert lower_bound(a, 4) == upper_bound(a, 4) == 4       # absent: both agree
    assert lower_bound(a, 0) == 0 and upper_bound(a, 99) == 6
    for x in range(-1, 11):                                  # matches the stdlib exactly
        assert lower_bound(a, x) == bisect.bisect_left(a, x)
        assert upper_bound(a, x) == bisect.bisect_right(a, x)
    assert lower_bound([], 5) == 0
    print("ok")

Recipes: everything is one bisect away

Section titled “Recipes: everything is one bisect away”

On a sorted list a (check the index is in bounds before reading a[i]):

Question Python Same in any language
how many < x bisect_left(a, x) lower bound
how many ≤ x bisect_right(a, x) upper bound
how many == x bisect_right(a, x) - bisect_left(a, x) upper − lower
is x present? i = bisect_left(a, x); i < len(a) and a[i] == x
smallest value ≥ x (ceiling) a[bisect_left(a, x)]
smallest value > x a[bisect_right(a, x)]
largest value ≤ x (floor) a[bisect_right(a, x) - 1]
largest value < x a[bisect_left(a, x) - 1]
all values in [lo, hi] a[bisect_left(a, lo):bisect_right(a, hi)]

The Python docs have the same recipes under “Searching Sorted Lists”. A good memory hook: left uses < and lands left of the run of x’s; right uses ≤ and lands right of it.

What each language gives you

Section titled “What each language gives you”
Python C# TypeScript
binary search on a sorted list bisect.bisect_left/right(a, x, lo, hi, *, key) (key since 3.10) List<T>.BinarySearch, Array.BinarySearch: index if found (any match among duplicates), else ~insertionPoint none: write lowerBound yourself
insert keeping order bisect.insort_left/right: O(n) list.Insert(~i, x): O(n) a.splice(i, 0, x): O(n)
sorted set, O(log n) changes sortedcontainers.SortedSet (third-party) SortedSet<T> (red-black tree; unique values; Min, Max, GetViewBetween, Reverse()) none
sorted map sortedcontainers.SortedDict (third-party) SortedDictionary<K,V> (red-black tree); SortedList<K,V> (sorted arrays: index access, O(n) insert) none (Map is insertion-ordered)
sorted multiset with indexing sortedcontainers.SortedList: add, remove, bisect_left/right, irange, sl[i] SortedDictionary<T,int> of counts, or SortedSet<(T, int id)> none
tour.py
import bisect


# --- stdlib only: a plain list kept sorted with bisect -------------------------------
xs: list[int] = []
for v in [50, 20, 40, 20, 10]:
    bisect.insort(xs, v)                     # O(log n) search + O(n) shift
assert xs == [10, 20, 20, 40, 50]


i, j = bisect.bisect_left(xs, 15), bisect.bisect_right(xs, 45)
assert xs[i:j] == [20, 20, 40]               # every value in [15, 45]: O(log n + k)


# key= (Python 3.10+): the list must already be sorted by that key.
people = [("ann", 31), ("bob", 25)]
people.sort(key=lambda p: p[1])
bisect.insort(people, ("cy", 28), key=lambda p: p[1])
assert [name for name, _ in people] == ["bob", "cy", "ann"]


# --- sortedcontainers (third-party, `pip install sortedcontainers`) --------------------
try:
    from sortedcontainers import SortedList


    sl = SortedList([50, 20, 40, 20, 10])    # duplicates allowed
    sl.add(30)                               # ~O(log n)
    assert list(sl.irange(15, 45)) == [20, 20, 30, 40]
    assert sl[0] == 10 and sl[-1] == 50      # index access, O(log n)
    sl.remove(20)                            # removes ONE occurrence
    assert sl.count(20) == 1
except ImportError:
    pass                                     # not installed: the stdlib part still ran
print("ok")

What TypeScript does without one

Section titled “What TypeScript does without one”

TypeScript and JavaScript have no sorted container, so pick the cheapest thing that meets the requirements:

  • Only need the min or max? Use a heap. It’s 30 lines and O(log n).
  • Few changes, many queries? Sorted array plus lowerBound. Inserts are O(n) but splice is a fast memory move.
  • Values are small integers? Bucket by value, or use a Fenwick tree indexed by value for counts and ranks.
  • All the data known up front? Sort once offline and answer queries in order.
  • Genuinely need O(log n) ordered inserts and deletes? Hand-roll a treap or skip list. Tell the interviewer that’s the plan and what you’d use in another language.

What it costs

Section titled “What it costs”
Operation Sorted array + bisect SortedList (Python, chunked) Balanced tree (SortedSet, SortedDictionary)
find position / contains O(log n) O(log n) O(log n)
insert / delete O(n) shift ~O(log n) amortized O(log n)
min / max O(1) O(1) O(log n)
k-th element O(1) O(log n) O(n) (no index)
range of k values O(log n + k) O(log n + k) O(log n + k)
memory tightest close to a list a node object per value

Python’s SortedList isn’t a tree: it’s a list of sorted sublists of about 1,000 items each, with an index on top. Shifting inside one small sublist is cheap, so it behaves like O(log n) in practice and is often faster than a tree because the data is contiguous.

Work to insert 10,000 values one at a time
drag the slider
Sorted array + bisect.insort / splice
25.1M
List of sorted chunks (SortedList)
2.6M
Balanced tree (SortedSet / SortedDictionary)
152.9K
Estimated element moves plus comparisons. A sorted array pays about n²/4 shifts in total. Shifts are a fast memmove, so up to ~10⁴-10⁵ items it often still wins in wall-clock time; past that the quadratic term takes over. Chunked lists and trees both stay near n log n.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • key= searches. Python 3.10+ bisect accepts key, but the list must already be sorted by that key, and insort(..., key=) inserts the whole item. Before 3.10, keep a parallel list of keys.
  • Tuples for ties. Store (value, id) to make equal values distinct and order them deterministically. This is also how to put duplicates into a C# SortedSet.
  • Binary search on the answer. Not a container at all: bisect over a range of candidate answers with a monotone yes/no check. See binary search.
  • Coordinate compression. Sort the distinct values once and replace each value by its index (bisect_left), so the values become 0..m−1 and fit an array or Fenwick tree.

Pitfalls

Section titled “Pitfalls”
  • Using bisect on unsorted data. It returns a position without any error. Sort first, or keep the invariant on every insert.
  • Left vs right mix-ups. “How many < x” is left; “how many ≤ x” is right. Test with a value that appears several times.
  • hi = n − 1. Then you can never return “insert at the end”. Keep hi = n and loop while lo < hi.
  • C# BinarySearch with duplicates returns some matching index, not the first. Write your own lower bound when it matters. When missing, decode the result with ~i.
  • C# SortedSet.Add silently rejects duplicates (returns false). Count them in a SortedDictionary or add a tie-breaking id.
  • JS .sort() without a comparator sorts numbers as strings.
  • Mutating a value inside a sorted container so its key changes. The container doesn’t notice; remove and re-insert instead.
  • (lo + hi) / 2 overflow in C# with huge int ranges. Use lo + (hi - lo) / 2.

In the interview

Section titled “In the interview”
  • Say which bound you mean before writing it: “I want the first index with value ≥ x, so lower bound.”
  • Ask whether sortedcontainers is available in Python. In C#, name SortedSet or SortedDictionary explicitly. In TS, say “no built-in, so I’ll keep a sorted array with binary search; inserts are O(n), and I’d switch to a treap if n gets large.”
  • Test the edges out loud: x smaller than everything, bigger than everything, present several times, empty list.
  • Expect follow-ups: “Inserts are now frequent, what changes?” (tree or chunked list), “Can you do it without the library?” (bisect + list, with its cost), “What if the data is too large for memory?” (a B-tree, or sorted files with binary search on disk).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
a = [2, 4, 4, 4, 7]. What are bisect_left(a, 4) and bisect_right(a, 4)?
Check yourself
pick one
On a sorted list a, how do you get the largest value ≤ x (the floor), assuming one exists?
Check yourself
pick one
You insert 10⁶ random values one at a time into a Python list with bisect.insort. What dominates the cost?

Practice on your own

Section titled “Practice on your own”

These are classic textbook exercises, not gym questions:

  • Find the first and last positions of a target in a sorted array with duplicates.
  • Return the k values closest to x from a sorted array.
  • Count pairs (i, j) with |a[i] − a[j]| ≤ d by sorting once and bisecting for each element.
  • Is there a pair of indices at most k apart whose values differ by at most t? Keep a sorted window.
  • Compute the h-index from a sorted list of citation counts with binary search.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Binary searchThe algorithm underneath, including searching on the answer.
Binary search trees / ordered mapsWhat SortedSet and SortedDictionary are inside.
Heaps and priority queuesCheaper when you only need the min or max.
Segment and Fenwick treesCounts and ranks over values with updates.