Block Search

Idea

Block Search combines indexing + sequential scan for large ordered arrays split into blocks. Blocks are ordered by a key (e.g., max per block); inside each block elements are unordered. Locate block via index, then sequentially scan inside.

When to use

• Large sequential tables
• Frequent lookups, few inserts/deletes

Algorithm

1. Split into $m$ blocks of size $k$ (last may be smaller).
2. Build index table storing max (or min) key per block.
3. Search: locate block via index, then scan inside.

Pseudo-code:

for i = 0 to m-1:
    if x <= index[i]:
        // sequential search in block i
        for j = block[i].start to block[i].end:
            if A[j] == x:
                return j
        break
return -1

Code Implementation

// Block search: index[] is the index table (max key per block),
// and each block covers the range [block * blockSize, block * blockSize + blockSize).
int BlockSearch(int A[], int n, int blockSize, int index[], int m, int key) {
    int block = -1;
    // (1) Locate the block through the index table (sequential search)
    for (int i = 0; i < m; i++) {
        if (key <= index[i]) {
            block = i;
            break;
        }
    }
    if (block == -1) return -1;  // larger than the max key of every block
    // (2) Search sequentially inside the block
    int start = block * blockSize;
    int end = (start + blockSize < n) ? start + blockSize : n;
    for (int j = start; j < end; j++) {
        if (A[j] == key) return j;
    }
    return -1;  // not found
}

Deriving the Average Search Length (ASL)

Suppose a table of length $n$ is split into $m$ blocks, each of length $s = \lceil n/m \rceil$. The blocks are connected by an index that is searched sequentially, and each block is also searched sequentially.

$ASL = ASL_{\text{index}} + ASL_{\text{block}} = \frac{m+1}{2} + \frac{s+1}{2}$

The minimum is reached when $m \approx s \approx \sqrt{n}$, that is, when the number of blocks and the block length are both $\sqrt{n}$:

$ASL_{min} = \sqrt{n} + 1$

This is exactly why block search reaches $O(\sqrt{n})$.

Complexity

• Build index: $O(n)$
• Search: $O(\sqrt{n})$ (when block count and block size are both $\sqrt{n}$)

Exercises

Exercise 1

Briefly state block search idea and scenarios.

Exercise 2

100 elements, 10 blocks of 10. Max comparisons?

Past exam

2018·408

What are the two steps of the block search process, and what is its efficiency?