just a blog post for summarising my algorithm learning course.

1. What is 1D Range Search?

Think of it as the extension of Symbol Table

• Range search: find all keys between k1 and k2.
• Range count: the number of keys between k1 and k2.

Application: Database queries.

Geometric: think of the keys as points on a line - range search/count then just means finding/counting the points that fall inside a given 1d interval. This shows up directly in database queries (WHERE k1 <= key AND key <= k2).

Here’s a small ordered symbol table built by inserting J C T A M F R one at a time, followed by a count and a search for the range D to N:

2. List/Array implementations

Before reaching for a BST, consider the two obvious data structures:

• Unordered list: insert is O(1) (just append), but a range search/count has to scan every key, so it’s O(N).
• Ordered array: insert has to shift elements to keep the array sorted, so it’s O(N), but a range search/count can binary search for the position of k1 and k2 and then just walk (or count) the keys in between.

N is the number of keys in the table, R is the number of keys that match the query. Neither elementary structure hits the goal row - a balanced BST does, as the next two sections show.

3. Range count in a BST

Reuse the rank(key) operation from an ordinary BST (the number of keys strictly less than key) to answer a range count in two rank queries:

public int size(Key lo, Key hi)
{
    if (contains(hi)) return rank(hi) - rank(lo) + 1;
    else              return rank(hi) - rank(lo);
}

For example, in this BST the rank of each key is shown in parentheses:

Running time: proportional to log N.

rank() walks a single search path, so size(lo, hi) only touches the nodes on the search path to lo plus the nodes on the search path to hi - both O(log N) in a balanced BST.

4. Range search in a BST

Range count only needs two ranks, but range search has to actually collect every matching key. The recursive strategy prunes whole subtrees that can’t contain a match:

• Recursively search the left subtree, but only if it could contain a key >= lo.
• Check whether the key at the current node falls in [lo, hi]; if so, add it to the result.
• Recursively search the right subtree, but only if it could contain a key <= hi.

private void range(Node x, Key lo, Key hi, Queue<Key> result)
{
    if (x == null) return;

    int cmplo = lo.compareTo(x.key);
    int cmphi = hi.compareTo(x.key);

    if (cmplo < 0)              range(x.left, lo, hi, result);
    if (cmplo <= 0 && cmphi >= 0) result.enqueue(x.key);
    if (cmphi > 0)               range(x.right, lo, hi, result);
}

Searching the same tree for the range [D..N]:

• Green nodes (J F M) fall inside [D..N] and are added to the result.
• Red nodes (C T R) are compared against but don’t match: C < D so its left subtree (A, greyed out) is skipped entirely, and T > N so its right subtree is skipped too.
• Grey nodes are never even visited - that’s the pruning at work.

Running time: proportional to R + log N.

The nodes examined are the search path to lo, plus the search path to hi, plus the R matches themselves - each of those three pieces is bounded, so the total stays close to R + log N even though the recursion visits the whole tree in the worst case (e.g. a query that matches every key).

5. Summary

Backed by a balanced BST (a red-black BST or a B-tree), 1d range search hits the goal row from the table above: O(log N) insert, O(log N) range count, and O(R + log N) range search - all without giving up any of the ordered symbol table’s other operations.