Binary Search & bisect — Use binary search conceptually and with the bisect module (intro) - Python

SECTION 1

Historical Context & Motivation

Imagine you need to look up a word in a dictionary. You wouldn't start on page one and read every single entry — you'd flip to roughly the middle, see if you've gone too far or not far enough, and then repeat. This intuitive strategy is exactly the idea behind binary search, one of the most fundamental algorithms in computer science. The concept has been used by humans for centuries, long before electronic computers existed, whenever people needed to locate information in an ordered collection.

~200 BCE • Earliest Divide-and-Conquer Ideas

Ancient Babylonian and Greek mathematicians used interval-halving techniques to approximate square roots, an early form of the bisection method.

1946 • First Published Binary Search

John Mauchly described the binary search algorithm for electronic computers, showing how it could quickly locate records in sorted data.

1960 • First Bug-Free Implementation

Despite its simplicity, it took nearly 14 years before a correct, bug-free binary search was published — highlighting how tricky edge cases can be.

2001 • Python's bisect Module Released

Python's standard library included the bisect module, giving developers a tested, optimized binary search tool without writing one from scratch.

The core question binary search answers is simple yet powerful: how can we find a target value in a sorted list as quickly as possible? A naïve approach — checking every element one by one — works, but it becomes painfully slow as the list grows. Binary search solves this by eliminating half the remaining possibilities with each comparison, turning a potentially enormous task into a manageable one.

SECTION 2

Core Principles & Definitions

Binary search relies on a few key ideas that work together. Before you can use it, you need to understand each one clearly. The algorithm's elegance comes from combining these principles into a simple loop that rapidly zeroes in on the answer.

Sorted Input Required

Binary search only works on data that is already sorted in ascending (or descending) order. If the data isn't sorted, you must sort it first or use a different algorithm.

Divide and Conquer

At each step, you compare the target to the middle element. If the target is smaller, discard the upper half. If larger, discard the lower half. This halving is what makes the algorithm fast.

Logarithmic Time

Because you cut the search space in half each time, the number of steps grows as log₂(n). A list of 1,000,000 items needs at most about 20 comparisons.

Two Pointers: low and high

The algorithm tracks two boundaries — low and high — that define the current search range. The midpoint is calculated as (low + high) // 2.

The bisect Module

Python's built-in bisect module provides ready-made functions like bisect_left() and insort() so you don't have to code binary search yourself.

✦

KEY TAKEAWAY

Think of binary search like a guessing game where your friend picks a number between 1 and 100, and after each guess they say "higher" or "lower." The smartest strategy is to always guess the middle of the remaining range. You'd find any number in at most 7 guesses — that's the power of halving the search space each time.

SECTION 3

Visual Explanation — How Binary Search Narrows Down

The following diagram shows binary search in action on a sorted list of eight numbers. We want to find the value 23. Watch how the highlighted search range (between low and high) shrinks by half at each step until the target is found.

Each step shows the sorted array with the current low, mid, and high pointers. Grayed-out elements have been eliminated. The yellow cell is the current midpoint being compared, and the green cell marks the found target.

Notice how quickly the search range collapses. In Step 1, all eight elements are candidates. After one comparison with the midpoint (14), we know 23 must be in the right half. After Step 2's comparison with 31, we narrow it down to a single element. By Step 3 we confirm the match — just 3 comparisons instead of up to 8. This efficiency becomes dramatic with larger datasets: a list of one million items needs at most about 20 comparisons.

SECTION 4

Mathematical Framework — Why Logarithmic?

The speed of binary search can be described precisely using Big-O notation, which tells us how the number of operations grows relative to the input size. Let's see why binary search is O(log n) and how that compares to a simple linear scan.

LINEAR SEARCH TIME COMPLEXITY

T_linear(n) = O(n)

In the worst case, a linear search checks every element. If n is the list size, you might need n comparisons.

BINARY SEARCH TIME COMPLEXITY

T_binary(n) = O(log₂ n)

Each step halves the search range. After k steps, the remaining size is n / 2^k. We stop when this equals 1, so k = log₂(n).

MIDPOINT CALCULATION

mid = low + (high − low) // 2

This formula avoids integer overflow that can occur with (low + high) // 2 when low and high are very large. In Python, integers have unlimited size, but this form is still considered best practice.

List Size (n)	Linear Search (worst case)	Binary Search (worst case)
10	10 comparisons	≈ 4 comparisons
1,000	1,000 comparisons	≈ 10 comparisons
1,000,000	1,000,000 comparisons	≈ 20 comparisons
1,000,000,000	1,000,000,000 comparisons	≈ 30 comparisons

Comparison of worst-case comparisons for linear vs. binary search

The table makes the difference crystal clear. A billion-element list that would require up to a billion checks with linear search can be handled by binary search in roughly 30 comparisons. That's the power of logarithmic growth — it barely increases even as the input size explodes.

SECTION 5

Python's bisect Module — Binary Search Made Easy

Python ships with a built-in module called bisect that implements binary search for you. Instead of writing the loop yourself (and risking off-by-one bugs), you can call functions from this module to find insertion points or insert values into sorted lists. The module provides four main functions that every Python programmer should know.

The four main functions of the bisect module. bisect_left and bisect_right return insertion indices; insort_left and insort_right actually insert the value into the list.

The critical difference between bisect_left and bisect_right matters when the list contains duplicate values. bisect_left returns the index before existing duplicates, while bisect_right returns the index after them. When there are no duplicates, both functions return the same index. The insort functions combine finding the position and inserting the element into one call, keeping the list sorted automatically.

💡

Quick Import

To use the bisect module, simply add import bisect at the top of your Python file. No installation is needed — it comes with Python's standard library.

SECTION 6

Worked Example — Binary Search by Hand and with bisect

Let's walk through a complete example. We have a sorted list of exam scores, and we want to find whether a score of 85 exists and where a new score of 72 should be inserted.

Finding 85 in a Sorted List Using Binary Search

1
Step 1 — Set Up the List and Pointers

Our sorted list is scores = [55, 62, 70, 78, 85, 91, 96]. We set low = 0 and high = 6 (the last valid index). Our target is 85.

low = 0, high = 6, target = 85
2
Step 2 — First Iteration: Calculate mid

Calculate mid = (0 + 6) // 2 = 3. The value at index 3 is scores[3] = 78. Since 78 < 85, our target is in the right half. Update low = mid + 1 = 4.

78 < 85 → search right half. low = 4, high = 6
3
Step 3 — Second Iteration: Recalculate mid

Calculate mid = (4 + 6) // 2 = 5. The value at index 5 is scores[5] = 91. Since 91 > 85, our target is in the left half. Update high = mid − 1 = 4.

91 > 85 → search left half. low = 4, high = 4
4
Step 4 — Third Iteration: Found!

Calculate mid = (4 + 4) // 2 = 4. The value at index 4 is scores[4] = 85. This matches our target! The function returns index 4.

Found 85 at index 4 in just 3 comparisons.
5
Step 5 — Using bisect to Insert 72

Now let's use the bisect module. Calling bisect.bisect_left(scores, 72) returns 3, meaning 72 should go at index 3 (between 70 and 78). Calling bisect.insort(scores, 72) inserts it directly, producing [55, 62, 70, 72, 78, 85, 91, 96].

bisect_left returns 3; insort places 72 at index 3 automatically.

SECTION 7

Strengths, Limitations & Comparisons

Binary search is powerful, but it isn't always the right tool. Understanding when to use it — and when not to — is just as important as knowing how it works. Let's compare it to other approaches and explore its trade-offs.

Feature	Binary Search	Linear Search
Time Complexity	O(log n) — very fast	O(n) — slow for large lists
Requires Sorted Data?	Yes — must be sorted first	No — works on any list
Best For	Large sorted datasets, repeated searches	Small lists, unsorted data, single searches
Implementation Difficulty	Moderate — off-by-one errors are common	Easy — simple loop
Space Complexity	O(1) — iterative version uses constant space	O(1)

Binary Search vs. Linear Search

⚖️

WHEN TO CHOOSE WHICH

Think of it like choosing between a GPS and walking around looking for a store. If you already have a map (sorted data), the GPS (binary search) gets you there fast. But if you don't have a map (unsorted data), the GPS is useless — you might as well just walk around and look (linear search). The cost of sorting first is O(n log n), so if you only need to search once, linear search on unsorted data may be more practical.

⚠

Common Pitfall

The most frequent bug in hand-written binary search is an off-by-one error — using high = mid instead of high = mid − 1, or checking low < high instead of low <= high. This can cause infinite loops or missed elements. Using Python's bisect module avoids these bugs entirely.

SECTION 8

Connection to Advanced Topics

Binary search isn't just for finding items in a list — the core principle of "eliminate half the possibilities" appears everywhere in computer science. Once you master basic binary search, you'll recognize the same pattern in more advanced data structures and algorithms.

Concept	Connection to Binary Search
Binary Search Trees (BSTs)	A tree data structure where each node's left children are smaller and right children are larger — the same halving logic, but stored in a tree instead of a flat list.
Binary Search on the Answer	A competitive programming technique where you binary search over possible answer values rather than indices, useful for optimization problems.
Merge Sort & Quick Sort	These O(n log n) sorting algorithms use divide-and-conquer — the same recursive halving strategy that makes binary search efficient.
Database Indexing	Real databases use B-trees (generalized binary search trees) to look up records without scanning every row — the same log-time idea at massive scale.

How binary search concepts extend into advanced CS topics

As you continue learning algorithms, pay attention to any time a problem can be framed as searching within a sorted or monotonic space. If you can define a condition that switches from False to True (or vice versa) at some boundary, binary search can likely find that boundary efficiently. This insight turns binary search from a simple list-lookup tool into a versatile problem-solving strategy.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Why can't binary search be used on an unsorted list? Explain what would go wrong if you tried to apply the algorithm to the list [8, 3, 11, 1, 7, 15, 2] while searching for 7.

Show answer

Binary search assumes that when the middle element is compared to the target, all elements to the left are smaller and all elements to the right are larger. In the unsorted list [8, 3, 11, 1, 7, 15, 2], the midpoint value is 1 (index 3). Since 7 > 1, binary search would discard the left half, but 7 is actually at index 4 which is in the right half — so it happens to work by luck here. However, if you searched for 3, the algorithm would look right of index 3 (since 3 > 1), but 3 is at index 1 on the left side and would be missed. Without sorted order, discarding half the list may throw away the target.

Question 2: BASIC CALCULATION

Given the sorted list [10, 20, 30, 40, 50, 60, 70, 80], trace through binary search to find 60. List the value of low, high, and mid at each step, and state how many comparisons are needed.

Show answer

Iteration 1: low=0, high=7, mid=3, arr[3]=40. Since 40 < 60, set low=4. Iteration 2: low=4, high=7, mid=5, arr[5]=60. Since 60 == 60, target found! The answer is at index 5 in just 2 comparisons. This is fewer than log₂(8)=3 because we got lucky and hit the target before the worst case. The worst case for 8 elements is 3 comparisons, but finding the target early is always possible.

Question 3: INTERMEDIATE

Write a Python function binary_search(arr, target) that returns the index of target in a sorted list arr, or -1 if not found. Do not use the bisect module.

Show answer

Here is a correct implementation: def binary_search(arr, target): low, high = 0, len(arr) - 1; while low <= high: mid = (low + high) // 2; if arr[mid] == target: return mid; elif arr[mid] < target: low = mid + 1; else: high = mid - 1; return -1. The key details are: (1) use <= in the while condition so that a single remaining element is still checked, (2) set low = mid + 1 and high = mid - 1 (not mid) to avoid infinite loops, and (3) return -1 after the loop ends to signal the target was not found.

Question 4: APPLIED

You're building a grade calculator. Given a sorted list of grade boundaries boundaries = [60, 70, 80, 90] and corresponding letter grades ['F', 'D', 'C', 'B', 'A'], use bisect.bisect() to determine the letter grade for a score of 75.

Show answer

Calling bisect.bisect(boundaries, 75) returns 2, because 75 would be inserted after 70 but before 80 in the boundaries list. Using this index to look up the grades list: grades[2] = 'C'. The complete code is: import bisect; boundaries = [60, 70, 80, 90]; grades = ['F', 'D', 'C', 'B', 'A']; score = 75; index = bisect.bisect(boundaries, score); letter = grades[index]; print(letter) # Output: 'C'. This is a classic real-world use of bisect — mapping a continuous value to a category using sorted boundaries.

Question 5: CRITICAL THINKING

Suppose you have a sorted list with 1,000 elements and you need to search for a value that is not in the list. How many comparisons will binary search make before concluding the value doesn't exist? Now consider: if you need to perform 500 individual searches on this same list, compare the total number of comparisons for (a) linear search each time vs. (b) binary search each time. Which approach is better and by how much?

Show answer

For a list of 1,000 elements, binary search makes at most ⌈log₂(1000)⌉ = 10 comparisons before low exceeds high, confirming the value is absent. For 500 searches: (a) Linear search worst case = 500 × 1,000 = 500,000 total comparisons. (b) Binary search worst case = 500 × 10 = 5,000 total comparisons. Binary search is 100× faster in this scenario. The advantage grows with list size — for 1,000,000 elements and 500 searches, linear search needs up to 500,000,000 comparisons while binary search needs only about 500 × 20 = 10,000. This demonstrates why binary search is essential for repeated lookups on large sorted datasets.

SUMMARY

Lesson Summary

Summary

Binary search is an efficient algorithm that finds a target value in a sorted list by repeatedly comparing the target to the middle element and discarding half the remaining candidates. This gives it a time complexity of O(log n), meaning a list of one million items needs at most about 20 comparisons — vastly faster than checking every element one by one with linear search's O(n). The algorithm uses two pointers (low and high) and a calculated mid to narrow the search range each iteration.

Python's built-in bisect module provides battle-tested implementations so you don't have to write binary search from scratch. Key functions include bisect_left() and bisect_right() for finding insertion points, and insort() for inserting values while maintaining sort order. Remember: binary search requires sorted data as a precondition, and the divide-and-conquer principle it uses appears throughout computer science — from binary search trees to merge sort to real-world database indexing.