Binary Search — Foundation for Indexing

Before building a B-tree, we need to understand binary search — the algorithm at the heart of every tree traversal. Each node in a B-tree uses binary search to find the right key or child pointer.

The Algorithm

Binary search finds a target value in a sorted array in O(log n) time:

function binary_search(array, target):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = (low + high) / 2
        if array[mid] == target:
            return mid          # found!
        elif array[mid] < target:
            low = mid + 1       # target is in right half
        else:
            high = mid - 1      # target is in left half
    return -1                   # not found

Why O(log n)?

Each comparison eliminates half the remaining elements:

Array: [1, 3, 5, 7, 9, 11, 13, 15]  (8 elements)
Search for 11:

Step 1: mid=7 → 7 < 11 → search right half [9, 11, 13, 15]
Step 2: mid=11 → 11 = 11 → FOUND at index 5

Only 2 comparisons for 8 elements (log2(8) = 3 max)

For 1 million elements, binary search needs at most 20 comparisons. Table scan needs up to 1 million.

Range Search

Binary search also enables efficient range queries. To find all values between low and high:

1. Binary search to find the first value >= low
2. Scan forward until you pass high

Array: [1, 3, 5, 7, 9, 11, 13, 15]
Range [5, 11]:

Step 1: Binary search for 5 → index 2
Step 2: Scan: 5, 7, 9, 11 → stop (13 > 11)
Result: [5, 7, 9, 11]

This is exactly how B-tree range scans work in practice.

Connection to B-Trees

In a B-tree, each node contains a sorted array of keys. When searching:

1. Arrive at a node
2. Binary search the keys within that node
3. If found, return the value
4. If not found, follow the child pointer between the appropriate keys

So B-tree search is binary search at each level of the tree. If the tree has depth d and each node has up to k keys, the total work is O(d * log k).

How SQLite Uses Binary Search

SQLite's B-tree implementation (btree.c) uses sqlite3BtreeMovetoUnpacked() which performs binary search within each page to find the right cell. The comparison function handles SQLite's type affinity rules.

Your Task

Implement BSEARCH for exact lookup and BSEARCH_RANGE for range queries on sorted integer arrays.