Binary Search and BSTs: Fast Lookups Without Hashing

Binary Search and BSTs: Fast Lookups Without Hashing

Last lesson, you sorted data. This lesson, you learn why that was worth the effort.

In Lesson 6, we spent considerable time understanding sorting algorithms, from the quadratic simplicity of bubble sort to the divide-and-conquer elegance of merge sort, and ultimately to Python's built-in Timsort. You built a leaderboard for the NetProbe project that ranked users by activity score, connection count, and join date. But here is the question I want you to sit with: what was the point of sorting that data? If you just wanted to display it in order, sure, sorting is the obvious answer. But sorted data unlocks something far more powerful than pretty output. It unlocks logarithmic search.

Think about what happens when you look up a word in a physical dictionary. You do not start at page one and read every entry until you find "recursion." You open the book roughly in the middle, see that you are at "M," realize "R" comes later, flip forward, and keep halving the remaining pages. You have been doing binary search your entire life. You just did not know it had a name. Today, we formalize that intuition, implement it in Python, and then build the data structure that keeps data sorted as you insert and delete: the binary search tree.

Sorted data is not just about prettier output. It changes what your code can do. I once worked on a Django project at a startup where the team stored user events in a list and filtered them with list comprehensions every time someone asked "show me all events between Tuesday and Friday." The list had 200,000 entries. Each query scanned all of them. Response time: 1.8 seconds. After switching to bisect_left and bisect_right on a pre-sorted list, the same query took 0.0003 seconds. We deleted 15 lines of filtering code and replaced them with two. That is what this lesson is about: doing less work by being smarter about how your data is organized.

What We Are Building

By the end of this lesson, you will have a complete binary search and BST toolkit, plus a new NetProbe feature that answers date-range queries in logarithmic time.

Here is what the finished output looks like when you run the comprehensive script:

--- Binary Search Demo ---
Searching for 42 in sorted list of 20 elements...
Found 42 at index 8 (took 4 comparisons)

--- bisect Module Demo ---
Insert position for 35: index 6
Range query [20, 50]: found 7 elements

--- BST Demo ---
In-order traversal: [5, 10, 15, 20, 25, 30, 35]
Search for 20: Found
Search for 99: Not Found
After deleting 20: [5, 10, 15, 25, 30, 35]

--- Balance Comparison ---
Balanced BST height: 3
Skewed BST height: 7
Same number of nodes, wildly different performance.

--- NetProbe: users-between command ---
Users who joined between 2025-03-01 and 2025-06-30:
  alice (joined 2025-03-15)
  bob (joined 2025-04-22)
  charlie (joined 2025-06-01)
Query time: O(log n + k) where k=3

That range query at the bottom is the money feature. Let us build up to it.

The Problem That Hashing Cannot Solve

Dictionaries are the fastest general-purpose lookup tool in Python, but they have a blind spot that will bite you in production.

In Lesson 2, we explored why dict and set are your best friends for point lookups. You want to find user "alice"? Hash the key, jump to the bucket, done. O(1). Beautiful. But try this: "find all users who joined between March 1st and June 30th." A dictionary cannot help you here. Hash functions are designed to scatter keys uniformly across memory. The hash of "2025-03-15" and the hash of "2025-03-16" land in completely unrelated buckets. There is no concept of "nearness" or "between" in a hash table. To answer a range query with a dict, you must iterate through every single key-value pair and check whether it falls in the range. That is O(n), and it is exactly the brute-force approach we should be embarrassed to ship.

This is not a theoretical limitation. It shows up constantly in real applications. Every e-commerce platform needs "show me orders from last week." Every analytics dashboard needs "events between 2pm and 5pm." Every social network needs "users who signed up this quarter." At Google, I worked on a logging pipeline where we needed to pull log entries from a specific time window. The logs were stored in a structure optimized for key-value access. Fetching a time range meant scanning millions of entries. The fix was embarrassingly simple: keep a sorted index by timestamp and use binary search to find the boundaries of any range query in O(log n) time. The infrastructure team had been throwing more machines at a problem that needed a better algorithm.

The core insight is this: sorted data preserves order relationships that hashing deliberately destroys. When data is sorted, you know that everything before index i is smaller and everything after is larger. That single property, the sorted invariant, is what makes binary search possible. And binary search is what makes range queries fast. This connects directly to what you built in Lesson 6: sorting was not just about display order. It was about creating a structure that supports fundamentally different, faster operations.

💡 Key Insight: Hash tables give you O(1) point lookups but O(n) range queries. Sorted data gives you O(log n) point lookups AND O(log n + k) range queries, where k is the number of results. If you need ranges, sorting wins.

Here is a comparison that makes the trade-off concrete:

The table reveals an important pattern: there is no universally best data structure. If your workload is pure point lookups and inserts, stick with a dictionary. If you need range queries, ordering, or min/max access, sorted data with binary search is the right tool. Most real systems need both, which is exactly why databases like PostgreSQL maintain both hash indexes and B-tree indexes on different columns. You do not pick one religion and stick with it. You profile your access patterns and pick the right tool for each one.

🤔 Think about it: You have a list of 1 million timestamps. You need to answer "how many events happened between 2pm and 3pm?" using a dict vs a sorted list. How many operations does each approach require?

Binary Search: Halving Your Way to O(log n)

Binary search is the most important algorithm you will ever learn, and most developers implement it wrong on their first try.

The idea is deceptively simple. You have a sorted list. You want to find a target value. Start in the middle. If the middle element equals the target, you are done. If the target is smaller, search the left half. If the target is larger, search the right half. Repeat until you find it or run out of elements. Each step eliminates half the remaining data, which is why the time complexity is O(log n). For a million elements, that is about 20 steps instead of a million. For a billion, about 30. The growth rate of log n is so slow that it feels almost like cheating.

Analogy Bridge: Binary search is like playing the number-guessing game. I am thinking of a number between 1 and 1000. You guess 500. I say "higher." You guess 750. I say "lower." You guess 625. Each guess eliminates half the remaining possibilities. In at most 10 guesses (log2(1000) is roughly 10), you nail it. Now imagine your friend plays the same game by guessing 1, then 2, then 3, working through every number linearly. You would finish your lunch before they finished guessing. That is the difference between O(log n) and O(n). This analogy holds up well for the halving mechanism, but it breaks down in one important way: in the guessing game, you pick midpoints loosely in your head. In binary search on an array, you compute the midpoint from concrete indices, and getting those index calculations wrong is where the bugs live.

⚠️ Common Pitfall: The classic binary search bug is computing the midpoint as (lo + hi) // 2. If lo and hi are both large integers, their sum can overflow in languages like C or Java. Python handles arbitrary-precision integers natively, so this specific bug will not bite you in Python, but the habit of writing lo + (hi - lo) // 2 is worth building because you will encounter it in interviews and in other languages. Java's Arrays.binarySearch had this exact overflow bug for nine years before Joshua Bloch fixed it in 2006.

Here is the wrong way to interact with sorted data, and I have seen this in production code more times than I care to admit:

# DON'T: Linear scan on sorted data
def find_user_linear(sorted_users, target_date):
    for user in sorted_users:
        if user.join_date == target_date:
            return user
    return None
# O(n) - you sorted the data and then ignored that fact

And here is what you should write instead:

# DO: Binary search on sorted data
def find_user_binary(sorted_dates, target_date):
    lo, hi = 0, len(sorted_dates) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if sorted_dates[mid] == target_date:
            return mid
        elif sorted_dates[mid] < target_date:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # not found
# O(log n) - respects the sorted invariant

The three conditions in that while loop are the heart of every binary search. First, lo <= hi ensures you still have a valid range to search. If lo passes hi, you have exhausted all possibilities and the target is not present. Second, the comparison at mid tells you which half to keep. Third, the updates lo = mid + 1 and hi = mid - 1 are crucial: if you write lo = mid instead of lo = mid + 1, you risk an infinite loop when lo and hi are adjacent. I spent two hours debugging this exact issue during a Google interview prep session years ago. The off-by-one error in binary search is so famous that Jon Bentley reported in "Programming Pearls" that only 10% of professional programmers could write a correct binary search on their first attempt. Donald Knuth called it "simple but not easy."

Remember from Lesson 5 how recursion works with base cases and recursive cases? Binary search has a natural recursive structure: the base case is when lo > hi (not found) or when sorted_dates[mid] == target (found), and the recursive case halves the search space by calling itself on either the left or right portion. You can absolutely write binary search recursively, and it maps cleanly to the recursive thinking patterns we practiced. However, I strongly prefer the iterative version for Python. Python has no tail-call optimization (remember, sys.getrecursionlimit defaults to 1000), so while a recursive binary search on a list of 10,000 elements would only need about 14 recursive calls (safely within the limit), the iterative version avoids the call stack overhead entirely and is cleaner to reason about.

💡 Key Takeaway: Binary search requires sorted data and achieves O(log n) by eliminating half the search space at each step. The iterative version is safer and simpler in Python.

Python's bisect Module: The Tool Most Developers Never Discover

Stop writing binary search from scratch. Python ships with a battle-tested implementation in the bisect module, and almost nobody uses it.

The bisect module has been in the Python standard library since Python 2.1, released in 2001. It provides four essential functions: bisect_left, bisect_right (also aliased as bisect), insort_left, and insort_right (also aliased as insort). These functions operate on sorted lists and maintain the sorted invariant automatically. The C implementation (_bisect in CPython) makes these functions faster than anything you would write in pure Python. Despite being available for over two decades, I routinely see intermediate Python developers who have never heard of it. They write manual loops over sorted data, or worse, they re-sort the entire list every time they insert a new element. The bisect module eliminates both of these anti-patterns.

Let me explain what each function does and when you need it. bisect_left(a, x) returns the leftmost index where x could be inserted into sorted list a while keeping it sorted. If x already exists in a, the index points to the position before (to the left of) the existing entry. bisect_right(a, x) returns the rightmost insertion point, meaning the position after (to the right of) any existing entries equal to x. The difference between left and right matters enormously when you have duplicates, and duplicates show up constantly in real data. If your sorted list is [10, 20, 20, 20, 30] and you call bisect_left(a, 20), you get index 1 (before the first 20). If you call bisect_right(a, 20), you get index 4 (after the last 20). This distinction is how you answer "how many 20s are there?" in O(log n) time: bisect_right(a, 20) - bisect_left(a, 20) gives you the count without scanning.

Here is where it gets powerful: range queries. To find all elements between lo_val and hi_val in a sorted list, you call bisect_left(a, lo_val) to get the start index and bisect_right(a, hi_val) to get the end index. Then a[start:end] gives you every element in that range. Two binary searches plus a slice. The time complexity is O(log n + k) where k is the number of elements in the range. Compare that to scanning the entire list at O(n). This is the exact operation we need for the NetProbe "users-between" command: find the left boundary of the start date, find the right boundary of the end date, slice.

For insertions, insort keeps your list sorted without re-sorting. bisect.insort(a, x) finds the correct position using binary search in O(log n) time and then inserts the element. The insertion itself is O(n) because list elements need to shift in memory, but for moderately sized lists (say, under 100,000 elements), this is still much faster than appending and re-sorting. Appending and sorting costs O(n log n) per insertion, while insort costs O(n) per insertion. That log n factor adds up quickly. At Stripe, their payment event processing uses a similar pattern internally: maintain a sorted buffer of recent transactions and use binary search insertion to keep it ordered as new transactions arrive, avoiding the overhead of full re-sorts.

The table shows a subtle but critical distinction between left and right. In most cases, insort (which defaults to insort_right) is what you want. It places new elements after any existing duplicates, which preserves insertion order among equal keys. Use insort_left when you specifically want new duplicates to appear before existing ones. For range queries, the pattern is always the same: bisect_left for the inclusive start, bisect_right for the inclusive end, then slice.

📌 Remember: bisect_left gives you "first position >= x" and bisect_right gives you "first position > x". For inclusive range queries [lo, hi], use bisect_left(a, lo) for the start and bisect_right(a, hi) for the end.

Peer Teaching Prompt: Explain binary search to a friend who has never heard of it, in exactly 3 sentences.

Now that you understand how to search and insert into sorted arrays efficiently, here is where things get interesting: what if you need those O(log n) operations but inserts and deletes are happening constantly? Shifting array elements on every write becomes the bottleneck. That is exactly the problem binary search trees were built to solve.

Binary Search Trees: Sorted Data That Stays Sorted

A BST is what you get when you combine the node-and-pointer structure of a linked list with the sorted invariant of binary search.

In Lesson 4, we built linked lists where each node had a value and a next pointer (and optionally a prev pointer for doubly linked lists). We learned that pointer-based structures allow O(1) insertions once you have the position, because you just rewire references instead of shifting array elements. A binary search tree uses the same fundamental concept but gives each node two pointers instead of one: left and right. The invariant that makes a BST special is this: for any node, every value in its left subtree is smaller, and every value in its right subtree is larger. This single rule, maintained at every node in the tree, is what enables O(log n) search without maintaining a sorted array.

Why do we need BSTs when we already have sorted lists with bisect? Because sorted lists have an Achilles heel: insertion and deletion both cost O(n) due to element shifting. When you call bisect.insort on a list of 1 million elements, the binary search part takes O(log n) steps to find the correct position, but the actual insertion requires CPython to shift all subsequent elements one position to the right, which is O(n). If you are inserting and deleting frequently, this O(n) cost dominates and your "fast" sorted list becomes sluggish. A BST solves this: insertion, deletion, and search are all O(log n) in a balanced tree, because you just create a new node and update two pointers instead of shifting half an array. This is exactly the trade-off we saw with linked lists in Lesson 4, where insertion was O(1) once you had the position, versus O(n) for arrays.

Let me walk you through the structure piece by piece. Each BST node holds three things: a value, a reference to a left child, and a reference to a right child. When you search for a value, you start at the root (the topmost node) and make the same binary decision as in binary search: go left if the target is smaller than the current node, go right if it is larger. Each comparison moves you one level deeper in the tree. If you reach a None child, the value is not in the tree. If the tree is balanced, its height is O(log n), so you make at most O(log n) comparisons before reaching the bottom. This is identical to binary search on an array, but the "array" is implicit in the tree structure itself.

In-order traversal is the magic trick of BSTs. If you visit nodes in the order left-subtree, current-node, right-subtree (the "in-order" pattern), you get all values in sorted order. This is a direct application of the recursion patterns from Lesson 5: the base case is when the node is None (do nothing), and the recursive case processes the left subtree, visits the current node, then processes the right subtree. Remember how we discussed the call stack in Lesson 5? An in-order traversal of a tree with height h will create h frames on the call stack at most, which is another reason balanced trees matter. A skewed tree with height n would push n frames, risking a stack overflow on large datasets. Interestingly, you can think of the recursive traversal as an implicit stack (from Lesson 3), where Python's call stack plays the role of the explicit stack data structure.

🤔 Think about it: In a BST, you insert values in this exact order: [10, 20, 30, 40, 50]. What does the tree look like? Now try [30, 10, 40, 20, 50]. What changes?

💡 Key Takeaway: A BST combines linked list flexibility (pointer-based insertion) with binary search efficiency (O(log n) lookup), but only when the tree is balanced.

The Balance Trap: When Insertion Order Destroys Your BST

The dirty secret of binary search trees is that they are only O(log n) on average. The worst case is O(n), exactly as slow as a linked list.

This is not a theoretical concern that only matters on whiteboards. I have personally seen a BST-based cache at a startup degrade from millisecond lookups to multi-second lookups because the data happened to arrive in near-sorted order. The team was caching product IDs that came from an auto-incrementing database primary key: 1001, 1002, 1003, and so on. When you insert sorted data into a plain BST, each new value is larger than everything already in the tree, so it always goes to the right child. The tree degenerates into a straight chain leaning entirely to the right. Searching for the most recently inserted element requires traversing the entire chain. The height, which determines lookup time, goes from O(log n) to O(n).

Let me put concrete numbers on this so you feel the pain. If you insert 10,000 elements in random order, the expected height of the BST is about 14 (roughly 2 times log2(10,000), due to a mathematical property of random BSTs). If you insert them in sorted order, the height is exactly 10,000. That means searching for the last element requires 10,000 comparisons instead of 14. A 700x performance difference from the exact same data structure, the exact same implementation, just because the insertion order changed. In production, you almost never control the insertion order. Data arrives from users, APIs, and event streams in whatever order it happens to come.

This balance problem connects to something we saw in Lesson 3 with stacks and queues. Remember how a stack's LIFO behavior means the order you push determines the order you pop? BSTs have an analogous property: the order you insert determines the shape of the tree, which determines the performance of every subsequent operation. A stack does not care whether you push 1-2-3 or 3-2-1, the push and pop operations are always O(1). But a BST cares deeply. Inserting 1, 2, 3, 4, 5 gives you O(n) search. Inserting 3, 1, 5, 2, 4 gives you O(log n) search. Same data, different order, wildly different outcomes.

The table makes the problem visceral. Two of those four scenarios give you linked-list performance from a tree data structure. In the median-first approach, you insert the median of the full dataset first, then the medians of the two halves, and so on. This produces a perfectly balanced tree, but it requires knowing all the data upfront, which defeats the purpose of dynamic insertion.

This is why self-balancing trees exist. AVL trees (invented by Adelson-Velsky and Landis in 1962), red-black trees (used by Java's TreeMap and C++'s std::map), and B-trees (used by virtually every database engine, including PostgreSQL, MySQL, and SQLite) all add extra rules that automatically restructure the tree after every insertion or deletion to maintain a height of O(log n). Red-black trees guarantee that the longest path from root to leaf is at most twice the length of the shortest path. B-trees, which are used in database indexes, allow multiple keys per node and are optimized for disk access patterns. These are beyond the scope of this lesson, but understanding why they exist, specifically to solve the balance trap, is essential.

Python does not include a BST in its standard library, and this is a deliberate choice. Guido van Rossum and the core developers decided that dict (hash table) and list with bisect cover the vast majority of use cases. If you need a self-balancing tree in Python, reach for the third-party package sortedcontainers. The SortedList class from sortedcontainers gives you O(log n) insertion, O(log n) search, and O(log n + k) range queries, all backed by a B-tree-like internal structure. Grant Jenks, the author, benchmarked it extensively against C-extension alternatives and found that the pure-Python approach was often faster due to better cache locality. This is a good reminder that Big-O is not the whole story: constant factors and memory access patterns matter in practice.

⚠️ Common Pitfall: Never benchmark a BST with only random input and conclude "BSTs are fast." Always test with worst-case (sorted) input. If your BST degrades to linked-list speed on sorted input and your production data might arrive sorted, you have a time bomb in your codebase.

Choosing Your Lookup Strategy: bisect vs dict vs BST

The most common mistake intermediate developers make is reaching for the same data structure for every problem. Let me give you a decision framework.

Here is a realistic scenario. You are building a user management system for a growing web application. You need three capabilities: (1) look up a user by username instantly, (2) find all users who joined between two dates, and (3) add new users as they sign up in real time. No single data structure handles all three requirements optimally. This is normal. Real systems use multiple data structures in concert, each serving the access pattern it was designed for.

How to read this table and make a real decision. For capability (1), point lookup by username, a dict is the clear winner at O(1). Nothing else comes close for pure key-value access. For capability (2), range queries by date, you need sorted data, so either a sorted list with bisect or a SortedList. For capability (3), frequent inserts, a sorted list with bisect has O(n) insertion cost due to element shifting, which becomes painful past 100,000 elements. The practical answer for most Python applications: use a dict for point lookups AND maintain a separate sorted list (with bisect.insort) for range queries. This is the dual-index pattern. You store the data once but index it twice, the same way a database maintains multiple indexes on a single table.

If you are in a coding interview, the answer is almost always bisect for sorted-array problems and a hand-rolled BST when they explicitly ask for tree operations. Interviewers love BST questions because they test recursion, pointer manipulation, and algorithmic thinking simultaneously. In production, I have never once written a BST from scratch for real user-facing code. I use bisect for simple cases and sortedcontainers.SortedList for complex ones. But understanding how BSTs work under the hood makes you a better engineer because it teaches you to think about invariants, balance, and the relationship between data structure shape and performance.

Decision Matrix: A realistic scenario. You are building a logging system. You receive 10,000 log entries per second. Users query "show me all ERROR logs from the last 5 minutes" about 100 times per second. The log entries arrive roughly in chronological order (but not perfectly, due to network delays).

The table tells the story. For a high-write, moderate-read workload like logging, the plain sorted list's O(n) insertion cost makes it unusable. The unsorted list's O(n) query cost is equally bad. SortedList from sortedcontainers offers the best balance with O(log n) on both sides. For our NetProbe project, where the user count is moderate (thousands, not millions) and inserts happen infrequently (user signup), bisect.insort on a plain list is perfectly fine. This is the engineering judgment call: pick the simplest solution that handles your actual scale, not the theoretical worst case.

💡 Key Insight: In practice, maintain two structures: a dict for O(1) key lookups and a sorted list with bisect for O(log n + k) range queries. This dual-index approach is how databases work internally.

🤔 Think about it: You have 50,000 user records. You need to answer 10,000 range queries ("users between date X and date Y") but only 100 point lookups. Should you use a dict or a sorted list?

Common Gotchas

These are the mistakes I see students and junior developers make repeatedly with binary search and BSTs. I have made most of them myself.

Gotcha 1: Forgetting that bisect requires a pre-sorted list. If you call bisect.bisect_left on an unsorted list, it will return an index without complaint. No error, no warning, no exception. The index will simply be wrong. The bisect module trusts you to provide sorted input. This is a design choice for performance: checking sortedness would add O(n) overhead to every call, defeating the purpose of O(log n) search. The most insidious version of this bug is when the list is mostly sorted but has a few out-of-place elements, perhaps because you used list.append instead of bisect.insort for a batch of new entries. The binary search will return incorrect results for some queries but not others, making the bug intermittent and hard to track down.

Gotcha 2: Off-by-one errors in binary search boundaries. The condition while lo <= hi versus while lo < hi produces subtly different behavior. With <=, you check every element including when the search space has exactly one element (lo == hi). With <, you skip that case, potentially missing the target. I default to lo <= hi with updates lo = mid + 1 and hi = mid - 1 because this pattern always terminates and always checks every element. If you use a different combination of loop condition and update rules, you need to reason carefully about termination. The safest approach: pick one pattern, memorize it, and use it everywhere. My pattern is while lo <= hi with mid + 1 and mid - 1 updates.

Gotcha 3: BST deletion with two children. This is the single operation that causes the most implementation bugs in BSTs. When deleting a node with two children, you must: (a) find the in-order successor (smallest node in the right subtree), (b) copy its value to the node being deleted, (c) recursively delete the successor from the right subtree. Forgetting step (c) leaves a duplicate value in the tree. Getting the parent pointer wrong in step (c) corrupts the tree structure. Test deletion thoroughly with at least these cases: deleting a leaf, deleting a node with one child, deleting a node with two children, and deleting the root node.

Gotcha 4: Using a plain BST with user-controlled input. If users can influence the insertion order (for example, inserting records with sequential IDs, timestamps, or alphabetically sorted names), a plain BST degenerates to O(n). This is not just a performance issue. It can be a security vulnerability. An attacker who knows you use a plain BST can craft input that forces worst-case behavior, creating a denial-of-service condition. Redis, for example, uses skip lists (a probabilistic balanced structure) instead of plain BSTs for its sorted sets, specifically to guarantee O(log n) regardless of input order.

Gotcha 5: Confusing bisect_left and bisect_right for range queries. For an inclusive range query [lo, hi] (meaning "find all x where lo <= x <= hi"), use bisect_left(a, lo) for the start and bisect_right(a, hi) for the end. If you accidentally use bisect_right for the start, you will skip elements equal to lo. If you use bisect_left for the end, you will skip elements equal to hi. I have seen this bug in a financial reporting system where the quarterly report was missing transactions that happened exactly on the quarter boundary dates.

⚠️ Common Pitfall: The bisect module works with any sorted sequence for searching, but insort only works with mutable sequences (lists). You cannot use insort on a tuple. If you try, you get a TypeError that says the object does not support item assignment.

Code Playground: Binary Search and BSTs in Action

Here is the single comprehensive script that ties together everything we covered. Copy it, run it, modify it. Every concept from this lesson, manual binary search, the bisect module, BST operations, balance analysis, and range queries, is demonstrated in one cohesive program.

"""
Binary Search and BSTs: Complete demonstration.
Covers: manual binary search, bisect module, BST operations,
balance analysis, and range queries.
Run this file directly: python lesson7_playground.py
"""
import bisect
from datetime import date


# --- Section 1: Manual Binary Search ---

def binary_search(sorted_list, target):
    """Find target in sorted_list, return (index, comparisons) or (-1, comparisons)."""
    lo, hi = 0, len(sorted_list) - 1
    comparisons = 0

    while lo <= hi:
        mid = lo + (hi - lo) // 2  # safe midpoint calculation
        comparisons += 1

        if sorted_list[mid] == target:
            return mid, comparisons
        elif sorted_list[mid] < target:
            lo = mid + 1  # target is in the right half
        else:
            hi = mid - 1  # target is in the left half

    return -1, comparisons  # not found


# --- Section 2: BST Implementation ---

class BSTNode:
    """A single node in a binary search tree."""

    def __init__(self, value):
        self.value = value
        self.left = None   # all values < self.value
        self.right = None  # all values > self.value


class BST:
    """Binary Search Tree with insert, search, delete, and traversal."""

    def __init__(self):
        self.root = None

    def insert(self, value):
        """Insert a value, maintaining the BST invariant."""
        if self.root is None:
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        """Recursively find the correct position and insert."""
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)
        # duplicates are ignored in this implementation

    def search(self, value):
        """Return True if value exists in the tree."""
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        """Recursively search following the BST invariant."""
        if node is None:
            return False  # base case: reached a dead end
        if value == node.value:
            return True   # base case: found it
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

    def delete(self, value):
        """Delete a value from the tree."""
        self.root = self._delete_recursive(self.root, value)

    def _delete_recursive(self, node, value):
        """Recursively find and delete, returning the updated subtree root."""
        if node is None:
            return None  # value not found, nothing to delete

        if value < node.value:
            node.left = self._delete_recursive(node.left, value)
        elif value > node.value:
            node.right = self._delete_recursive(node.right, value)
        else:
            # Found the node to delete - handle three cases

            # Case 1 & 2: zero or one child
            if node.left is None:
                return node.right  # replace with right child (or None)
            if node.right is None:
                return node.left   # replace with left child

            # Case 3: two children - find in-order successor
            successor = node.right
            while successor.left is not None:
                successor = successor.left  # smallest in right subtree

            node.value = successor.value  # copy successor value here
            node.right = self._delete_recursive(
                node.right, successor.value  # then remove the successor
            )

        return node

    def inorder(self):
        """Return all values in sorted order via in-order traversal."""
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, node, result):
        """Left -> Current -> Right gives sorted output."""
        if node is None:
            return  # base case
        self._inorder_recursive(node.left, result)
        result.append(node.value)
        self._inorder_recursive(node.right, result)

    def height(self):
        """Return the height of the tree (0 for empty)."""
        return self._height_recursive(self.root)

    def _height_recursive(self, node):
        """Height = 1 + max(left height, right height)."""
        if node is None:
            return 0
        return 1 + max(
            self._height_recursive(node.left),
            self._height_recursive(node.right)
        )


# --- Section 3: Range Queries with bisect ---

def range_query(sorted_list, lo_val, hi_val):
    """Find all elements where lo_val <= element <= hi_val."""
    start = bisect.bisect_left(sorted_list, lo_val)   # first index >= lo_val
    end = bisect.bisect_right(sorted_list, hi_val)     # first index > hi_val
    return sorted_list[start:end]  # O(log n + k) total


# --- Section 4: Full Demonstration ---

def main():
    # -- Demo 1: Manual binary search --
    print("--- Binary Search Demo ---")
    data = sorted([3, 7, 11, 15, 19, 23, 27, 31, 42, 46,
                   50, 55, 60, 65, 70, 75, 80, 85, 90, 95])
    target = 42
    idx, comps = binary_search(data, target)
    print(f"Searching for {target} in sorted list of {len(data)} elements...")
    print(f"Found {target} at index {idx} (took {comps} comparisons)")

    # -- Demo 2: bisect module --
    print("\n--- bisect Module Demo ---")
    values = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60]
    insert_pos = bisect.bisect_left(values, 35)
    print(f"Insert position for 35: index {insert_pos}")

    result = range_query(values, 20, 50)
    print(f"Range query [20, 50]: found {len(result)} elements: {result}")

    # Counting duplicates with bisect
    dupes = [10, 20, 20, 20, 30, 30, 40]
    count_20 = bisect.bisect_right(dupes, 20) - bisect.bisect_left(dupes, 20)
    print(f"Count of 20 in {dupes}: {count_20}")

    # -- Demo 3: BST operations --
    print("\n--- BST Demo ---")
    tree = BST()
    for val in [20, 10, 30, 5, 15, 25, 35]:  # balanced insertion order
        tree.insert(val)

    print(f"In-order traversal: {tree.inorder()}")
    print(f"Search for 20: {'Found' if tree.search(20) else 'Not Found'}")
    print(f"Search for 99: {'Found' if tree.search(99) else 'Not Found'}")

    tree.delete(20)  # delete node with two children (root)
    print(f"After deleting 20: {tree.inorder()}")

    # -- Demo 4: Balance comparison --
    print("\n--- Balance Comparison ---")
    balanced_tree = BST()
    for val in [50, 25, 75, 12, 37, 62, 87]:  # median-first order
        balanced_tree.insert(val)

    skewed_tree = BST()
    for val in [10, 20, 30, 40, 50, 60, 70]:  # sorted order = worst case
        skewed_tree.insert(val)

    print(f"Balanced BST height: {balanced_tree.height()}")
    print(f"Skewed BST height: {skewed_tree.height()}")
    print("Same 7 nodes, wildly different performance.")

    # -- Demo 5: Date range query with bisect --
    print("\n--- Date Range Query Demo ---")
    users = [("alice", date(2025, 3, 15)),
        ("bob", date(2025, 4, 22)),
        ("diana", date(2025, 1, 5)),
        ("charlie", date(2025, 6, 1)),
        ("eve", date(2025, 8, 30)),]

    # Build sorted list using bisect.insort
    user_by_date = []  # list of (date, username) tuples
    for username, join_date in users:
        bisect.insort(user_by_date, (join_date, username))

    print("All users sorted by join date:")
    for d, name in user_by_date:
        print(f"  {name} (joined {d})")

    # Range query: who joined between March and June?
    range_start = date(2025, 3, 1)
    range_end = date(2025, 6, 30)
    start_idx = bisect.bisect_left(user_by_date, (range_start,))
    end_idx = bisect.bisect_right(user_by_date, (range_end, "~"))

    print(f"\nUsers who joined between {range_start} and {range_end}:")
    matches = user_by_date[start_idx:end_idx]
    for d, name in matches:
        print(f"  {name} (joined {d})")
    print(f"Query time: O(log n + k) where k={len(matches)}")


if __name__ == "__main__":
    main()

Expected output:

--- Binary Search Demo ---
Searching for 42 in sorted list of 20 elements...
Found 42 at index 8 (took 4 comparisons)

--- bisect Module Demo ---
Insert position for 35: index 6
Range query [20, 50]: found 7 elements: [20, 25, 30, 35, 40, 45, 50]
Count of 20 in [10, 20, 20, 20, 30, 30, 40]: 3

--- BST Demo ---
In-order traversal: [5, 10, 15, 20, 25, 30, 35]
Search for 20: Found
Search for 99: Not Found
After deleting 20: [5, 10, 15, 25, 30, 35]

--- Balance Comparison ---
Balanced BST height: 3
Skewed BST height: 7
Same 7 nodes, wildly different performance.

--- Date Range Query Demo ---
All users sorted by join date:
  diana (joined 2025-01-05)
  alice (joined 2025-03-15)
  bob (joined 2025-04-22)
  charlie (joined 2025-06-01)
  eve (joined 2025-08-30)

Users who joined between 2025-03-01 and 2025-06-30:
  alice (joined 2025-03-15)
  bob (joined 2025-04-22)
  charlie (joined 2025-06-01)
Query time: O(log n + k) where k=3

Walk through this output carefully. In Demo 1, binary search found 42 in only 4 comparisons out of 20 elements. That is the power of halving. In Demo 2, the duplicate counting found three 20s using two bisect calls, zero iteration. In Demo 4, both trees have 7 nodes, but the balanced tree has height 3 while the skewed tree has height 7, a 2.3x height difference that becomes a 700x difference at 10,000 nodes. In Demo 5, the date range query finds 3 matching users without scanning the entire list.

🔨 Project Update

Time to add date-based range queries to NetProbe. We are building on the sorted user list from Lesson 6's leaderboard and adding two new features: bisect.insort to maintain users sorted by join date, and a users-between command that finds all users who joined within a date range using O(log n + k) binary search.

Here is the cumulative NetProbe project code. New additions for this lesson are marked with # NEW IN LESSON 7 comments.

"""
NetProbe - Network Analysis Tool (Cumulative: Lessons 1-7)
A progressive project for learning Python data structures.
"""
import bisect
from collections import deque
from datetime import date
from operator import attrgetter


# --- User Model ---

class User:
    """Represents a network user with connections and activity."""

    def __init__(self, username, email, join_date, activity_score=0):
        self.username = username
        self.email = email
        self.join_date = join_date
        self.activity_score = activity_score
        self.connections = []  # list of connected usernames

    def __repr__(self):
        return f"User({self.username!r}, joined={self.join_date})"


# --- NetProbe Core ---

class NetProbe:
    """Network analysis tool using multiple data structures."""

    def __init__(self):
        # Lesson 2: dict for O(1) username lookup
        self.users_by_name = {}

        # Lesson 3: deque for recent activity log (bounded queue)
        self.activity_log = deque(maxlen=50)

        # Lesson 3: list-as-stack for command undo history
        self.command_history = []

        # NEW IN LESSON 7: sorted list of (join_date, username) for range queries
        self.users_by_date = []

    # --- Lesson 2: User Management ---

    def add_user(self, username, email, join_date, activity_score=0):
        """Add a user with O(1) dict insertion and sorted date insertion."""
        if username in self.users_by_name:
            print(f"  Error: User '{username}' already exists.")
            return

        user = User(username, email, join_date, activity_score)
        self.users_by_name[username] = user

        # NEW IN LESSON 7: maintain sorted order by join_date using bisect
        bisect.insort(self.users_by_date, (join_date, username))

        self.command_history.append(("add_user", username))  # Lesson 3: stack
        self.activity_log.append(f"Added user: {username}")  # Lesson 3: queue
        print(f"  Added user: {username} (joined {join_date})")

    def get_user(self, username):
        """O(1) lookup by username via dict."""
        return self.users_by_name.get(username)

    # --- Lesson 4: Connection Management ---

    def add_connection(self, user1, user2):
        """Add a bidirectional connection between two users."""
        u1 = self.get_user(user1)
        u2 = self.get_user(user2)
        if u1 is None or u2 is None:
            print(f"  Error: One or both users not found.")
            return
        if user2 not in u1.connections:
            u1.connections.append(user2)
        if user1 not in u2.connections:
            u2.connections.append(user1)
        self.activity_log.append(f"Connected: {user1} <-> {user2}")
        print(f"  Connected: {user1} <-> {user2}")

    # --- Lesson 6: Leaderboard (Sorting) ---

    def leaderboard(self, top_n=5):
        """Display top users by activity score, connections, and join date."""
        all_users = list(self.users_by_name.values())
        ranked = sorted(
            all_users,
            key=lambda u: (-u.activity_score, -len(u.connections), u.join_date)
        )
        print(f"\n  === Leaderboard (Top {top_n}) ===")
        for i, user in enumerate(ranked[:top_n], 1):
            print(f"  {i}. {user.username} | score={user.activity_score} "
                  f"| connections={len(user.connections)} "
                  f"| joined={user.join_date}")

    # --- NEW IN LESSON 7: Date Range Queries ---

    def users_between(self, start_date, end_date):
        """Find all users who joined between start_date and end_date (inclusive).

        Uses bisect_left and bisect_right for O(log n + k) performance
        where n is total users and k is the number of matches.
        """
        # bisect_left finds the first entry >= (start_date,)
        lo = bisect.bisect_left(self.users_by_date, (start_date,))

        # bisect_right finds the first entry > (end_date, "~")
        # "~" (tilde, ord 126) sorts after all ASCII letters
        hi = bisect.bisect_right(self.users_by_date, (end_date, "~"))

        matches = self.users_by_date[lo:hi]

        print(f"\n  === Users joined {start_date} to {end_date} ===")
        if not matches:
            print("  No users found in this date range.")
        else:
            for join_date, username in matches:
                user = self.users_by_name[username]
                print(f"  {username} | joined={join_date} "
                      f"| score={user.activity_score}")
        print(f"  ({len(matches)} found, O(log n + k) query)")
        return matches

    # --- NEW IN LESSON 7: Chronological Listing ---

    def list_users_chronological(self):
        """List all users in join-date order using the pre-sorted list."""
        print("\n  === Users by Join Date ===")
        for join_date, username in self.users_by_date:
            print(f"  {username} | joined={join_date}")

    # --- Utility ---

    def show_recent_activity(self, count=10):
        """Show recent activity from the bounded deque (Lesson 3)."""
        print(f"\n  === Recent Activity (last {count}) ===")
        recent = list(self.activity_log)[-count:]
        for entry in recent:
            print(f"  - {entry}")


# --- Main: Run the cumulative project ---

def main():
    print("=" * 55)
    print("  NetProbe - Network Analysis Tool (Lessons 1-7)")
    print("=" * 55)

    probe = NetProbe()

    # --- Add users ---
    print("\n[Adding Users]")
    probe.add_user("alice", "alice@example.com",
                   date(2025, 3, 15), activity_score=85)
    probe.add_user("bob", "bob@example.com",
                   date(2025, 4, 22), activity_score=92)
    probe.add_user("charlie", "charlie@example.com",
                   date(2025, 6, 1), activity_score=78)
    probe.add_user("diana", "diana@example.com",
                   date(2025, 1, 5), activity_score=95)
    probe.add_user("eve", "eve@example.com",
                   date(2025, 8, 30), activity_score=60)
    probe.add_user("frank", "frank@example.com",
                   date(2025, 2, 14), activity_score=88)
    probe.add_user("grace", "grace@example.com",
                   date(2025, 7, 19), activity_score=71)
    probe.add_user("hank", "hank@example.com",
                   date(2025, 11, 2), activity_score=55)

    # --- Add connections ---
    print("\n[Adding Connections]")
    probe.add_connection("alice", "bob")
    probe.add_connection("alice", "charlie")
    probe.add_connection("bob", "diana")
    probe.add_connection("charlie", "eve")
    probe.add_connection("diana", "frank")

    # --- Lesson 6: Leaderboard ---
    probe.leaderboard(top_n=5)

    # --- NEW IN LESSON 7: Chronological listing ---
    probe.list_users_chronological()

    # --- NEW IN LESSON 7: Range queries ---
    print("\n[Range Query: Q1 2025 (Jan-Mar)]")
    probe.users_between(date(2025, 1, 1), date(2025, 3, 31))

    print("\n[Range Query: Q2 2025 (Apr-Jun)]")
    probe.users_between(date(2025, 4, 1), date(2025, 6, 30))

    print("\n[Range Query: Summer 2025 (Jun-Aug)]")
    probe.users_between(date(2025, 6, 1), date(2025, 8, 31))

    print("\n[Range Query: No results (Dec)]")
    probe.users_between(date(2025, 12, 1), date(2025, 12, 31))

    # --- Recent activity log ---
    probe.show_recent_activity()

    print("\n" + "=" * 55)
    print("  All systems operational. Run complete.")
    print("=" * 55)


if __name__ == "__main__":
    main()

Expected output:

=======================================================
  NetProbe - Network Analysis Tool (Lessons 1-7)
=======================================================

[Adding Users]
  Added user: alice (joined 2025-03-15)
  Added user: bob (joined 2025-04-22)
  Added user: charlie (joined 2025-06-01)
  Added user: diana (joined 2025-01-05)
  Added user: eve (joined 2025-08-30)
  Added user: frank (joined 2025-02-14)
  Added user: grace (joined 2025-07-19)
  Added user: hank (joined 2025-11-02)

[Adding Connections]
  Connected: alice <-> bob
  Connected: alice <-> charlie
  Connected: bob <-> diana
  Connected: charlie <-> eve
  Connected: diana <-> frank

  === Leaderboard (Top 5) ===
  1. diana | score=95 | connections=2 | joined=2025-01-05
  2. bob | score=92 | connections=2 | joined=2025-04-22
  3. frank | score=88 | connections=1 | joined=2025-02-14
  4. alice | score=85 | connections=2 | joined=2025-03-15
  5. charlie | score=78 | connections=2 | joined=2025-06-01

  === Users by Join Date ===
  diana | joined=2025-01-05
  frank | joined=2025-02-14
  alice | joined=2025-03-15
  bob | joined=2025-04-22
  charlie | joined=2025-06-01
  grace | joined=2025-07-19
  eve | joined=2025-08-30
  hank | joined=2025-11-02

[Range Query: Q1 2025 (Jan-Mar)]

  === Users joined 2025-01-01 to 2025-03-31 ===
  diana | joined=2025-01-05 | score=95
  frank | joined=2025-02-14 | score=88
  alice | joined=2025-03-15 | score=85
  (3 found, O(log n + k) query)

[Range Query: Q2 2025 (Apr-Jun)]

  === Users joined 2025-04-01 to 2025-06-30 ===
  bob | joined=2025-04-22 | score=92
  charlie | joined=2025-06-01 | score=78
  (2 found, O(log n + k) query)

[Range Query: Summer 2025 (Jun-Aug)]

  === Users joined 2025-06-01 to 2025-08-31 ===
  charlie | joined=2025-06-01 | score=78
  grace | joined=2025-07-19 | score=71
  eve | joined=2025-08-30 | score=60
  (3 found, O(log n + k) query)

[Range Query: No results (Dec)]

  === Users joined 2025-12-01 to 2025-12-31 ===
  No users found in this date range.
  (0 found, O(log n + k) query)

  === Recent Activity (last 10) ===
  - Added user: charlie
  - Added user: diana
  - Added user: eve
  - Added user: frank
  - Added user: grace
  - Added user: hank
  - Connected: alice <-> bob
  - Connected: alice <-> charlie
  - Connected: bob <-> diana
  - Connected: charlie <-> eve

=======================================================
  All systems operational. Run complete.
=======================================================

Run the project you have built so far. Every user is inserted in chronological order via bisect.insort, and range queries use bisect_left/bisect_right to find matching users in O(log n + k) time. Notice how the Q1 query instantly returns 3 users without scanning all 8. With 100,000 users, this would still take about 17 comparisons to find the range boundaries. The dual-index pattern is clearly visible: users_by_name (dict) handles point lookups, and users_by_date (sorted list) handles range queries. Each data structure serves the access pattern it was designed for.

Extending It

What if we wanted to add more query dimensions? The pattern scales by maintaining additional sorted lists. Need to query by activity score? Maintain a second sorted list of (activity_score, username) tuples with bisect.insort. Need to find the top 10 most active users in a date range? First use the date-sorted list to find users in the range, then sort that small subset by activity score. This two-step approach (index scan plus filter) is exactly what database query planners do. Pick the most selective index first to narrow the candidate set, then apply additional filters on the smaller result.

What about real-time updates with heavy write traffic? If users change their activity scores frequently, maintaining a sorted list becomes expensive because you need to remove the old entry and insert the new one. Removal from a list is O(n) (you have to find it and shift elements), and insertion via insort is also O(n). At that point, consider sortedcontainers.SortedList, which handles both removals and insertions in O(log n). You install it with pip install sortedcontainers and replace your bisect.insort calls with SortedList.add. The API is intuitive: sl.irange(minimum, maximum) gives you a range query iterator directly, no manual index arithmetic needed.

For the interview-oriented reader, here is how this knowledge translates directly. LeetCode problems 34 (Find First and Last Position of Element in Sorted Array), 35 (Search Insert Position), and 704 (Binary Search) are all direct applications of what you learned today. Problem 35 is literally bisect_left. Problem 34 is bisect_left for the first position and bisect_right(a, x) - 1 for the last position. Knowing the bisect module means you can solve these in two lines of Python instead of writing manual binary search and risking off-by-one errors under interview pressure.

💡 Key Takeaway: The sorted-list-with-bisect pattern scales to multiple dimensions by maintaining parallel sorted lists. For heavy write workloads, upgrade to sortedcontainers.SortedList.

Summary Table

Now that you have binary search and BSTs in your toolkit, Lesson 8 will introduce heaps and priority queues. A heap is another tree-based structure, but instead of the BST invariant (left smaller, right larger), it uses the heap property: the parent is always smaller than (or larger than) both children. This makes heaps perfect for "find the top K" problems, which show up everywhere from recommendation engines to network monitoring dashboards. You will add a "top-k active users" feature to NetProbe using Python's heapq module, which stores the heap as a plain list (no node objects needed) and gives you O(log n) push and pop with O(1) access to the minimum element.

def count_in_range(sorted_list, lo, hi):
    """Count elements where lo <= element <= hi in O(log n)."""
    return bisect.bisect_right(sorted_list, hi) - bisect.bisect_left(sorted_list, lo)

import bisect
import time

class RateLimiter:
    def __init__(self, window_seconds=60, prune_seconds=300):
        self.requests = {}  # username -> sorted list of timestamps
        self.window = window_seconds
        self.prune_after = prune_seconds

    def record(self, username):
        if username not in self.requests:
            self.requests[username] = []
        bisect.insort(self.requests[username], time.time())

    def count_recent(self, username):
        if username not in self.requests:
            return 0
        timestamps = self.requests[username]
        cutoff = time.time() - self.window
        idx = bisect.bisect_left(timestamps, cutoff)
        return len(timestamps) - idx

    def prune(self, username):
        if username not in self.requests:
            return
        cutoff = time.time() - self.prune_after
        idx = bisect.bisect_left(self.requests[username], cutoff)
        self.requests[username] = self.requests[username][idx:]