AlgorithmsBeginner

Binary Search

Q: For a sorted list [1, 2, 2, 2, 3], what index does bisect_left(2) return versus bisect_right(2), and why are they different?

`bisect_left` returns 1, the insertion point before every existing 2, so inserting there keeps all 2s together immediately after it. `bisect_right` returns 4, the insertion point after every existing 2, keeping all 2s together immediately before it. They differ because they define the insertion point by a different partition rule, `bisect_left` guarantees everything before the returned index is strictly less than the target, `bisect_right` guarantees everything before the returned index is less than or equal to it, so the choice determines whether a new equal-valued element gets inserted before or after existing equal elements, not just where "some 2" is found.

Q: Why does binary search require the input to already be sorted, and what actually happens if you run it on unsorted data?

Binary search's core logic is comparing the target against a midpoint and eliminating the entire half that can't possibly contain it, an elimination step that's only valid if elements are ordered, so everything below the midpoint really is smaller and everything above really is larger. Run it on unsorted data and there's no error or exception, the algorithm has no way to detect the invariant is broken, it just keeps halving the search space based on comparisons that no longer imply anything real, and returns an insertion point or "not found" result that has no actual relationship to whether or where the target exists in the list.

Q: Why is binary search O(log n) instead of O(n), and what specifically has to be true about the data structure for that to hold?

Each comparison eliminates half of the remaining search space, so after k comparisons only n/2^k elements remain to check, meaning the search terminates once 2^k ≥ n, k ≈ log2(n) comparisons, exponentially fewer than checking every element one at a time. That guarantee depends entirely on being able to jump directly to a midpoint in constant time, which is true for an array or list with O(1) random access, but not for a data structure like a linked list where reaching the "middle" element itself takes O(n) time, on a linked list, binary search's comparison-count advantage is real but gets erased by the cost of just navigating there.

Why bisect_left and bisect_right return different insertion points for the exact same value, and why binary search silently returns a wrong answer, not an error, the moment the input isn't actually sorted.

Updated 2026-07-243 min read

On this page

Overview

Binary search finds a target (or its correct insertion point) in a sorted sequence by repeatedly comparing against a midpoint and discarding the half that can't contain the answer, which is what makes it O(log n) instead of O(n), each comparison eliminates half the remaining space rather than checking one element at a time. That halving logic is only valid because the data is sorted; run it on unsorted input and there's no error, the algorithm simply has no way to detect the broken invariant and returns a result with no real relationship to the actual data. Python's bisect_left and bisect_right both do this same search but define slightly different insertion points for a value that already appears in the list, before or after the existing equal entries, which matters directly for keeping equal-valued elements grouped consistently on repeated insertion.

Quick Reference

Function	Insertion point for an existing value	Guarantee
`bisect_left`	Before all existing equal entries	Everything before the index is strictly `<` target
`bisect_right` (`bisect`)	After all existing equal entries	Everything before the index is `<=` target

Syntax

python

import bisect

sorted_list = [1, 2, 2, 2, 3]
bisect.bisect_left(sorted_list, 2)   # 1
bisect.bisect_right(sorted_list, 2)  # 4

Examples

python

# Binary search on unsorted data doesn't error; it just returns
# a meaningless result, since the halving logic assumes order.
import bisect
unsorted = [5, 1, 4, 2, 3]
bisect.bisect_left(unsorted, 3)
# No exception - but this index has no real meaning here.

Binary search fails silently on unsorted input

There's no runtime check for sortedness, an unsorted list produces a wrong-but-plausible-looking result rather than an error. The invariant is the caller's responsibility to maintain, not something the algorithm verifies.

Visual Diagram

Why binary search is O(log n)

Common Mistakes

Running binary search (or bisect) on data that isn't actually sorted and trusting the result, since nothing detects or errors on the broken invariant.
Confusing bisect_left and bisect_right when the exact insertion position relative to existing equal values matters (e.g., maintaining insertion order among duplicates).
Applying binary search to a linked list or other structure without O(1) random access, losing the whole advantage since reaching the midpoint itself costs O(n).
Forgetting binary search needs the comparison direction consistent with how the data is actually sorted (ascending vs. descending).

Performance

Binary search's O(log n) advantage over a linear O(n) scan is dramatic at scale, roughly 20 comparisons for a million-element sorted array versus up to a million.
That advantage depends entirely on O(1) random access to the midpoint; on a data structure without it, the navigation cost can dominate and erase the algorithmic benefit.

Best Practices

Verify data is actually sorted before relying on binary search, since there's no runtime check that will catch the mistake for you.
Choose bisect_left or bisect_right deliberately based on whether new equal-valued entries should land before or after existing ones.
Reach for binary search specifically on structures with O(1) random access (arrays, lists); it doesn't deliver its usual advantage on linked structures.
Prefer a language's built-in binary search implementation (like bisect) over hand-rolling one, off-by-one errors in manual binary search are a classic, well-documented source of bugs.

Interview questions

For a sorted list [1, 2, 2, 2, 3], what index does bisect_left(2) return versus bisect_right(2), and why are they different?

`bisect_left` returns 1, the insertion point before every existing 2, so inserting there keeps all 2s together immediately after it. `bisect_right` returns 4, the insertion point after every existing 2, keeping all 2s together immediately before it. They differ because they define the insertion point by a different partition rule, `bisect_left` guarantees everything before the returned index is strictly less than the target, `bisect_right` guarantees everything before the returned index is less than or equal to it, so the choice determines whether a new equal-valued element gets inserted before or after existing equal elements, not just where "some 2" is found.

Why does binary search require the input to already be sorted, and what actually happens if you run it on unsorted data?

Binary search's core logic is comparing the target against a midpoint and eliminating the entire half that can't possibly contain it, an elimination step that's only valid if elements are ordered, so everything below the midpoint really is smaller and everything above really is larger. Run it on unsorted data and there's no error or exception, the algorithm has no way to detect the invariant is broken, it just keeps halving the search space based on comparisons that no longer imply anything real, and returns an insertion point or "not found" result that has no actual relationship to whether or where the target exists in the list.

Why is binary search O(log n) instead of O(n), and what specifically has to be true about the data structure for that to hold?

Each comparison eliminates half of the remaining search space, so after k comparisons only n/2^k elements remain to check, meaning the search terminates once 2^k ≥ n, k ≈ log2(n) comparisons, exponentially fewer than checking every element one at a time. That guarantee depends entirely on being able to jump directly to a midpoint in constant time, which is true for an array or list with O(1) random access, but not for a data structure like a linked list where reaching the "middle" element itself takes O(n) time, on a linked list, binary search's comparison-count advantage is real but gets erased by the cost of just navigating there.

References

Python Documentation - bisect Module

AlgorithmsBeginner

Big O Notation

How to read and reason about Big O time and space complexity, with the common growth rates ranked and worked examples for each.

Updated 2026-07-18

3 min read

AlgorithmsIntermediate

Dynamic Programming

Why caching subproblem solutions turns an exponential naive recursive Fibonacci into a linear one, and what "overlapping subproblems" actually has to be true about a problem before memoization can help at all.

Updated 2026-07-24

3 min read

AlgorithmsIntermediate

Sorting Algorithms & Stability

Why a "stable" sort guarantees equal-key elements keep their original relative order, and how Python's Timsort exploits already-sorted runs in real data to hit O(n) on the best case instead of always paying O(n log n).

Updated 2026-07-24

3 min read

AlgorithmsIntermediate

Graph Traversal: BFS & DFS

Why breadth-first search's queue explores every neighbor before any of their children, guaranteeing the shortest path in an unweighted graph, while depth-first search's stack (or recursion) does the opposite and can't make that guarantee at all.

Updated 2026-07-24

3 min read

Announcement