Week 6 — Search and Hashing¶

CEN207 Data Structures (formerly CE205) · Fall 2026–2027

Click inside the slides and use the arrow keys; use the button at the bottom right of the slides, or the "Open slides full screen" link above, for full screen.

0. Before we start¶

0.1 What you already know¶

Two ideas from the last five weeks matter most this week.

From Week 1 — arrays and indices. An array stores its elements in one contiguous block of memory, and arr[i] is computed directly as base_address + i * element_size — no searching required to reach index i, only to decide which i holds what you want. Every search technique this week (jump, interpolation, exponential, Fibonacci) is a different strategy for choosing which indices to check, on a sorted array, to find that i in as few comparisons as possible. Binary search, already familiar to you, is one point in this design space; this week fills in the rest of it.

From Week 4 — halving a search space. Binary search's big idea — eliminate half the remaining candidates with a single comparison, giving O(log n) total comparisons — is the yardstick every technique in this chapter is measured against. Jump search deliberately does worse than binary search (in exchange for simplicity); interpolation search does better on the right kind of data; exponential search adapts binary search to array sizes you do not know in advance; Fibonacci search matches binary search's asymptotic cost using only addition and subtraction. Keep binary search's O(log n) in your head as the reference point for all four.

A genuinely new idea: trading order for computation. Every technique above still works by comparing target against array elements and narrowing a range. Hashing throws that whole approach away: instead of narrowing, a hash function computes directly where a key belongs, in one O(1) step, with no order requirement on the data at all. The price is that two different keys can compute to the same location — a collision — and the second half of this week is entirely about handling that.

0.2 The map of this week¶

flowchart TD
    W6["Week 6: Search and Hashing"]
    W6 --> S["Beyond binary search (still comparison-based, still need a SORTED array)"]
    S --> S1["Jump search: fixed-size blocks, O(sqrt n)"]
    S --> S2["Interpolation search: a formula estimates the position"]
    S --> S3["Exponential search: double a bound, then binary search inside it"]
    S --> S4["Fibonacci search: split with Fibonacci numbers, only +/-"]
    W6 --> H["Hashing: compute the location instead of comparing for it"]
    H --> H1["Hash function: h(k) = k mod m (division method)"]
    H --> H2["Collisions are unavoidable -- two keys, one slot"]
    H2 --> C1["Separate chaining: a linked list per slot"]
    H2 --> C2["Open addressing: the key lives IN the table"]
    C2 --> O1["Linear probing: h, h+1, h+2, ... (primary clustering)"]
    C2 --> O2["Quadratic probing: h+1^2, h+2^2, ... (needs m prime, alpha <= 0.5)"]
    C2 --> O3["Double hashing: h1(k), step h2(k) (best spread in practice)"]
    H --> R["Rehashing: grow the table when it fills up, amortized O(1) insert"]

Every box gets its own section below, most with a step-by-step animation, a complete C and Java program, and a note on complexity and common mistakes.

1. The search problem, and a recap of linear and binary search¶

1.1 The problem, restated¶

You already solved the basic version of this problem in Week 1: given an array and a target value, is target in the array, and if so, at which index? Week 1 gave you two answers — linear search (check every element, O(n)) and binary search (on a sorted array, repeatedly check the middle and discard half, O(log n)). This week's question is sharper: given that the array is sorted, is binary search's O(log n) really the best we can do, and what does it cost to do better, or to do almost as well with a simpler idea? The four new techniques below each answer that question differently.

1.2 Recap: linear search, O(n)¶

Linear search makes no assumption about the data at all: it checks arr[0], then arr[1], and so on, until it finds target or runs out of array. Its cost is proportional to n, the array's size, in the worst case (the target is last, or absent) and on average (for a target present at a uniformly random position, you check n/2 elements on average). Its one great virtue is that it works on any array, sorted or not — every technique from here on trades that generality away in exchange for speed, by requiring the array to be sorted first.

1.3 Recap: binary search, O(log n)¶

Binary search requires a sorted array. It checks the middle element; if it is the target, done; if the target is smaller, the entire right half — including the middle — can be discarded in one step (sorted order guarantees the target cannot be there); if larger, the left half is discarded the same way. Each comparison halves the remaining candidates, so after k comparisons at most n / 2^k candidates remain; the search ends when that reaches 1, giving k = log2(n) comparisons in the worst case — O(log n). For n = 1,000,000, that is about 20 comparisons, versus up to a million for linear search on the same data.

If binary search, its complexity, and its C/Java code are not fresh in your memory, revisit Week 1 before continuing — this chapter assumes it and will not re-derive it. The four techniques below all still require a sorted array, and all are still fundamentally comparison-based; none of them beats binary search's O(log n) worst case by more than a constant factor except interpolation search on the right kind of data (and even that has a bad worst case, as you will see in section 3).

2. Jump search¶

2.1 A question to start¶

Binary search's jump to the exact middle is powerful, but it needs a division (or a shift) and a bit of careful index arithmetic (lo + (hi - lo) / 2, to avoid overflow) at every single step, and it does not access memory sequentially — it jumps all over the array, which is unfriendly to hardware that likes to read memory in contiguous blocks (a fact you will meet in more depth when this course reaches memory hierarchies and caching). What if, instead, you scanned forward in fixed-size blocks — check every k-th element, and once you have jumped past where target must be, fall back to a plain linear scan of just that one block? That is jump search: simpler arithmetic than binary search, sequential memory access within each block, at the cost of being asymptotically slower than binary search (though still far faster than linear search).

This block-style search appears in Donald Knuth's The Art of Computer Programming, Volume 3: Sorting and Searching (1973) as an alternative to binary search, presented specifically as a case where a simple calculus argument — minimizing the sum of two costs — determines the algorithm's one free parameter, the block size.

2.2 The idea and the right block size¶

Pick a block size b. Check arr[b-1], arr[2b-1], arr[3b-1], … until you find a boundary that is >= target (or run off the end of the array); target, if present, must be in the block just before that boundary (sorted order again). Then scan that one block linearly, left to right, comparing every element.

How many comparisons does this cost in the worst case? Jumping costs at most n / b comparisons (you jump through the whole array in blocks of size b), and the final linear scan costs at most b comparisons. Total: n/b + b. Calculus (or just trying values) shows this sum is minimized when b = sqrt(n), giving a total worst-case cost of 2 * sqrt(n) — O(sqrt(n)). That is worse than binary search's O(log n) (for n = 1,000,000, sqrt(n) = 1000 versus log2(n) ≈ 20), but far better than linear search's O(n), and the arithmetic at each step is a single addition, not a division.

2.3 In memory, and the code¶

Below, jump_search computes block = floor(sqrt(n)), jumps forward one block at a time by checking the last index of each block, and once it finds a block whose last index is >= target, scans that block linearly.

int jump_search(const int arr[], int n, int target, int *comparisons) {
    int block = (int) sqrt((double) n);      /* block size = floor(sqrt(n)) */
    if (block < 1) block = 1;
    int prev = 0, step = block, comp = 0;
    while (step < n) {                        /* jump forward one block at a time */
        comp++;
        if (arr[step - 1] >= target) break;    /* target may be in this block */
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    for (int i = prev; i < step; i++) {        /* linear scan inside the block */
        comp++;
        if (arr[i] == target) { *comparisons = comp; return i; }
        if (arr[i] > target) break;             /* sorted: no need to look further */
    }
    *comparisons = comp;
    return -1;
}

static int jumpSearch(int[] arr, int target) {
    int n = arr.length;
    int block = (int) Math.sqrt(n);          // block size = floor(sqrt(n))
    if (block < 1) block = 1;
    int prev = 0, step = block;
    comparisons = 0;
    while (step < n) {                        // jump forward one block at a time
        comparisons++;
        if (arr[step - 1] >= target) break;    // target may be in this block
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    for (int i = prev; i < step; i++) {        // linear scan inside the block
        comparisons++;
        if (arr[i] == target) return i;
        if (arr[i] > target) break;             // sorted: no need to look further
    }
    return -1;
}

Play the animation to watch the block boundaries get checked one by one, then the final block scanned left to right.

In the picker, also try target near the last block, needs the most jumps (hard) and the edge cases target is smaller than every value, target is larger than every value, and target is in range but not in the array — or press 🎲 for random data at four difficulty levels, or type your own sorted array and target.

2.4 Try it¶

/* Week 6 -- Search and Hashing
 * Jump search: on a SORTED array, jump forward in fixed-size blocks
 * (block = floor(sqrt(n))) until a block boundary is >= target, then scan
 * that block linearly. Prints every jump and every comparison inside the
 * final block.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <math.h>

int jump_search(const int arr[], int n, int target, int *comparisons) {
    int block = (int) sqrt((double) n);      /* block size = floor(sqrt(n)) */
    if (block < 1) block = 1;
    int prev = 0, step = block, comp = 0;
    while (step < n) {                        /* jump forward one block at a time */
        comp++;
        printf("  jump: check arr[%d] = %d\n", step - 1, arr[step - 1]);
        if (arr[step - 1] >= target) break;    /* target may be in this block */
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    printf("  scanning block [%d..%d)\n", prev, step);
    for (int i = prev; i < step; i++) {        /* linear scan inside the block */
        comp++;
        printf("  compare arr[%d] = %d\n", i, arr[i]);
        if (arr[i] == target) { *comparisons = comp; return i; }
        if (arr[i] > target) break;             /* sorted: no need to look further */
    }
    *comparisons = comp;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int comparisons = 0;
    int index = jump_search(arr, n, target, &comparisons);
    if (index == -1) printf("result: not found, %d comparisons\n\n", comparisons);
    else printf("result: found at index %d, %d comparisons\n\n", index, comparisons);
}

int main(void) {
    int a[] = {2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62};
    int n = 16;

    run_scenario("normal: 16 values, target found in the second block", a, n, 42);
    run_scenario("hard: target near the last block, needs the most jumps", a, n, 58);
    run_scenario("edge: target is smaller than every value", a, n, 1);
    run_scenario("edge: target is larger than every value", a, n, 999);
    run_scenario("edge: target is in range but not in the array", a, n, 45);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Jump search: on a SORTED array, jump forward in fixed-size blocks
 * (block = floor(sqrt(n))) until a block boundary is >= target, then scan
 * that block linearly. Prints every jump and every comparison inside the
 * final block.
 * CEN207 Data Structures (formerly CE205)
 */
public class JumpSearch {
    static int comparisons;

    static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int block = (int) Math.sqrt(n);          // block size = floor(sqrt(n))
        if (block < 1) block = 1;
        int prev = 0, step = block;
        comparisons = 0;
        while (step < n) {                        // jump forward one block at a time
            comparisons++;
            System.out.println("  jump: check arr[" + (step - 1) + "] = " + arr[step - 1]);
            if (arr[step - 1] >= target) break;    // target may be in this block
            prev = step;
            step += block;
        }
        if (step > n) step = n;
        System.out.println("  scanning block [" + prev + ".." + step + ")");
        for (int i = prev; i < step; i++) {        // linear scan inside the block
            comparisons++;
            System.out.println("  compare arr[" + i + "] = " + arr[i]);
            if (arr[i] == target) return i;
            if (arr[i] > target) break;             // sorted: no need to look further
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = jumpSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + comparisons + " comparisons");
        else System.out.println("result: found at index " + index + ", " + comparisons + " comparisons");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62};

        runScenario("normal: 16 values, target found in the second block", a, 42);
        runScenario("hard: target near the last block, needs the most jumps", a, 58);
        runScenario("edge: target is smaller than every value", a, 1);
        runScenario("edge: target is larger than every value", a, 999);
        runScenario("edge: target is in range but not in the array", a, 45);
    }
}

Try it

gcc -std=c11 -Wall -Wextra -o /tmp/x jump_search.c && /tmp/x

-- normal: 16 values, target found in the second block --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 42
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [8..12)
  compare arr[8] = 34
  compare arr[9] = 38
  compare arr[10] = 42
result: found at index 10, 6 comparisons

-- hard: target near the last block, needs the most jumps --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 58
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [12..16)
  compare arr[12] = 50
  compare arr[13] = 54
  compare arr[14] = 58
result: found at index 14, 6 comparisons

-- edge: target is smaller than every value --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 1
  jump: check arr[3] = 14
  scanning block [0..4)
  compare arr[0] = 2
result: not found, 2 comparisons

-- edge: target is larger than every value --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 999
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [12..16)
  compare arr[12] = 50
  compare arr[13] = 54
  compare arr[14] = 58
  compare arr[15] = 62
result: not found, 7 comparisons

-- edge: target is in range but not in the array --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 45
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [8..12)
  compare arr[8] = 34
  compare arr[9] = 38
  compare arr[10] = 42
  compare arr[11] = 46
result: not found, 7 comparisons

javac -Xlint:all -d /tmp/j JumpSearch.java && java -cp /tmp/j JumpSearch

2.5 Complexity, mistakes, self-check¶

Complexity. Best case O(1) (target is the very first block boundary checked and happens to be the target itself — rare, since the boundary check is >=, not ==). Worst case and average case both O(sqrt(n)), with the optimal block size b = sqrt(n) derived in section 2.2. It needs a sorted array, just like binary search.

3. Interpolation search¶

3.1 A question to start¶

Think about how you look up a name in a paper phone book (or a word in a printed dictionary). You do not open it exactly in the middle every time, the way binary search would. If you are looking for "Yilmaz", you open the book much closer to the end; if you are looking for "Aydin", much closer to the start. You are using the fact that names are not just sorted, but roughly uniformly spread out across the alphabet, to jump straight to a good estimate of the right page. Interpolation search does exactly this on a sorted array of numbers: instead of always checking the middle, it computes an estimated position with a formula, using how far target sits between the smallest and largest values currently in range.

This position-estimating idea for searching ordered data appears in W. W. Peterson's 1957 paper Addressing for Random-Access Storage (IBM Journal of Research and Development) — the same early paper that laid out foundational ideas for organizing random-access storage that this week's later sections on hashing also draw on — and was subsequently formalized and analyzed under the name interpolation search.

3.2 The formula¶

Within the current range [lo..hi], assume the values are roughly evenly spaced between arr[lo] and arr[hi]. Then target's position can be estimated proportionally:

pos = lo + floor( (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]) )

If target == arr[lo], this gives pos = lo; if target == arr[hi], it gives pos = hi; for a value in between, it estimates linearly. Compare arr[pos] to target exactly as binary search compares arr[mid]: equal, done; less, narrow to [pos+1..hi]; greater, narrow to [lo..pos-1]. One extra case needs a guard: if arr[hi] == arr[lo], the formula's denominator is zero — a division by zero — which can only happen when the whole current range holds one repeated value; the guard catches this case and resolves it directly, without ever evaluating the formula.

3.3 Cost: excellent on uniform data, poor on skewed data¶

On data that really is close to uniformly spread, interpolation search's estimate lands very close to the true position almost every time, giving an average-case cost of O(log log n) — for n = 1,000,000, log2(n) ≈ 20 but log2(log2(n)) ≈ 4.3: a handful of probes instead of about twenty. But the formula's accuracy depends entirely on the uniform spread assumption. On skewed data — say, sixteen small values clustered together plus one enormous outlier — the formula's estimate is pulled far off target by that one outlier, and interpolation search's worst case degrades all the way to O(n), no better than linear search. Interpolation search is a bet: it wins big on well-behaved numeric data (phone numbers, sensor readings, timestamps) and loses badly on adversarial or heavily skewed data.

3.4 In memory, and the code¶

int interpolation_search(const int arr[], int n, int target, int *probes) {
    int lo = 0, hi = n - 1, p = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        p++;
        if (arr[hi] == arr[lo]) {                 /* guard: avoid division by zero */
            *probes = p;
            return lo;                            /* target must equal arr[lo] here */
        }
        /* widen to long long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
           when the array spans values near INT_MIN and INT_MAX at once */
        long long span = (long long) arr[hi] - (long long) arr[lo];
        long long num = (long long) target - (long long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        if (arr[pos] == target) { *probes = p; return pos; }
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    *probes = p;
    return -1;
}

static int interpolationSearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    probes = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        probes++;
        if (arr[hi] == arr[lo]) {                 // guard: avoid division by zero
            return lo;                            // target must equal arr[lo] here
        }
        // widen to long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
        // when the array spans values near Integer.MIN_VALUE and Integer.MAX_VALUE at once
        long span = (long) arr[hi] - (long) arr[lo];
        long num = (long) target - (long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

In the picker, also try slightly uneven spacing, needs a few probes (hard) and the edge cases skewed data: last value is huge, many probes, all values equal: the division guard kicks in, and target is entirely outside the range: rejected on sight — or press 🎲 for random data, or type your own sorted array.

3.5 Try it¶

/* Week 6 -- Search and Hashing
 * Interpolation search: on a SORTED, roughly uniform array, estimate where
 * the target should be with a formula instead of always checking the
 * middle. A guard avoids dividing by zero when the current range is all one
 * value. Prints every probe.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

int interpolation_search(const int arr[], int n, int target, int *probes) {
    int lo = 0, hi = n - 1, p = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        p++;
        if (arr[hi] == arr[lo]) {                 /* guard: avoid division by zero */
            printf("  probe %d: arr[hi] == arr[lo] (%d), guard triggered\n", p, arr[lo]);
            *probes = p;
            return lo;                            /* target must equal arr[lo] here */
        }
        /* widen to long long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
           when the array spans values near INT_MIN and INT_MAX at once */
        long long span = (long long) arr[hi] - (long long) arr[lo];
        long long num = (long long) target - (long long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        printf("  probe %d: lo=%d hi=%d pos=%d arr[pos]=%d\n", p, lo, hi, pos, arr[pos]);
        if (arr[pos] == target) { *probes = p; return pos; }
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    *probes = p;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int probes = 0;
    int index = interpolation_search(arr, n, target, &probes);
    if (index == -1) printf("result: not found, %d probes\n\n", probes);
    else printf("result: found at index %d, %d probes\n\n", index, probes);
}

int main(void) {
    int normal[] = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85};
    int hard[] = {10, 13, 21, 24, 33, 36, 44, 48, 55, 61, 68, 74, 81, 87, 94, 100};
    int skewed[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1000000};
    int all_equal[] = {42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42};

    run_scenario("normal: uniformly spread 16 values, found in a single probe", normal, 16, 55);
    run_scenario("hard: slightly uneven spacing, needs a few probes", hard, 16, 81);
    run_scenario("edge: skewed data, last value is huge, many probes", skewed, 16, 8);
    run_scenario("edge: all values equal, the division guard kicks in", all_equal, 16, 42);
    run_scenario("edge: target is entirely outside the range, rejected on sight", normal, 16, 999);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Interpolation search: on a SORTED, roughly uniform array, estimate where
 * the target should be with a formula instead of always checking the
 * middle. A guard avoids dividing by zero when the current range is all one
 * value. Prints every probe.
 * CEN207 Data Structures (formerly CE205)
 */
public class InterpolationSearch {
    static int probes;

    static int interpolationSearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        probes = 0;
        while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
            probes++;
            if (arr[hi] == arr[lo]) {                 // guard: avoid division by zero
                System.out.println("  probe " + probes + ": arr[hi] == arr[lo] (" + arr[lo] + "), guard triggered");
                return lo;                            // target must equal arr[lo] here
            }
            // widen to long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
            // when the array spans values near Integer.MIN_VALUE and Integer.MAX_VALUE at once
            long span = (long) arr[hi] - (long) arr[lo];
            long num = (long) target - (long) arr[lo];
            int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
            System.out.println("  probe " + probes + ": lo=" + lo + " hi=" + hi + " pos=" + pos + " arr[pos]=" + arr[pos]);
            if (arr[pos] == target) return pos;
            if (arr[pos] < target) lo = pos + 1;
            else hi = pos - 1;
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = interpolationSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + probes + " probes");
        else System.out.println("result: found at index " + index + ", " + probes + " probes");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85};
        int[] hard = {10, 13, 21, 24, 33, 36, 44, 48, 55, 61, 68, 74, 81, 87, 94, 100};
        int[] skewed = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1000000};
        int[] allEqual = {42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42};

        runScenario("normal: uniformly spread 16 values, found in a single probe", normal, 55);
        runScenario("hard: slightly uneven spacing, needs a few probes", hard, 81);
        runScenario("edge: skewed data, last value is huge, many probes", skewed, 8);
        runScenario("edge: all values equal, the division guard kicks in", allEqual, 42);
        runScenario("edge: target is entirely outside the range, rejected on sight", normal, 999);
    }
}

Try it

gcc -std=c11 -Wall -Wextra -o /tmp/x interpolation_search.c && /tmp/x

-- normal: uniformly spread 16 values, found in a single probe --
arr = 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
target = 55
  probe 1: lo=0 hi=15 pos=9 arr[pos]=55
result: found at index 9, 1 probes

-- hard: slightly uneven spacing, needs a few probes --
arr = 10 13 21 24 33 36 44 48 55 61 68 74 81 87 94 100
target = 81
  probe 1: lo=0 hi=15 pos=11 arr[pos]=74
  probe 2: lo=12 hi=15 pos=12 arr[pos]=81
result: found at index 12, 2 probes

-- edge: skewed data, last value is huge, many probes --
arr = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1000000
target = 8
  probe 1: lo=0 hi=15 pos=0 arr[pos]=1
  probe 2: lo=1 hi=15 pos=1 arr[pos]=2
  probe 3: lo=2 hi=15 pos=2 arr[pos]=3
  probe 4: lo=3 hi=15 pos=3 arr[pos]=4
  probe 5: lo=4 hi=15 pos=4 arr[pos]=5
  probe 6: lo=5 hi=15 pos=5 arr[pos]=6
  probe 7: lo=6 hi=15 pos=6 arr[pos]=7
  probe 8: lo=7 hi=15 pos=7 arr[pos]=8
result: found at index 7, 8 probes

-- edge: all values equal, the division guard kicks in --
arr = 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42
target = 42
  probe 1: arr[hi] == arr[lo] (42), guard triggered
result: found at index 0, 1 probes

-- edge: target is entirely outside the range, rejected on sight --
arr = 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
target = 999
result: not found, 0 probes

javac -Xlint:all -d /tmp/j InterpolationSearch.java && java -cp /tmp/j InterpolationSearch

3.6 Complexity, mistakes, self-check¶

Complexity. Average case O(log log n) on uniformly distributed data; worst case O(n) on skewed data (the array [1, 2, 3, ..., 15, 1000000] above needed 8 probes for just 16 elements — imagine the same shape scaled up to a million elements). Needs a sorted array, exactly like binary search.

4. Exponential search¶

4.1 A question to start¶

Binary search needs to know n, the array's size, before it starts, to compute the first midpoint. But what if the array is effectively unbounded — a sorted stream, or an array so enormous that just reading n is itself expensive — and you strongly suspect the target, if present, is somewhere near the front? Scanning the whole thing to find n first would be wasteful. Exponential search solves this: find a bound that is guaranteed to contain the target by doubling (1, 2, 4, 8, …) until you overshoot it, then run ordinary binary search inside that bound. The bound-finding phase costs only O(log index) — proportional to how far in the target actually is — not O(log n).

Jon Bentley and Andrew Yao published this technique in their 1976 paper An Almost Optimal Algorithm for Unbounded Searching (Information Processing Letters). It is also called unbounded search or galloping search — "galloping" for the doubling bound-finding phase, small steps that grow larger and larger like a horse picking up speed — and variants of it are used today inside several merge and set-intersection algorithms.

4.2 The idea: double until you overshoot, then binary search¶

Check arr[0] first (comparison #1). If it is not the target, grow a bound by doubling — 1, 2, 4, 8, … — checking arr[bound] each time, until arr[bound] >= target or bound >= n. At that point, target, if present, must lie in [bound/2, min(bound, n-1)] — because the previous, smaller bound was checked and found < target. Run ordinary binary search inside exactly that range.

4.3 In memory, and the code¶

int exponential_search(const int arr[], int n, int target, int *comparisons) {
    if (n <= 0) { *comparisons = 0; return -1; }    /* nothing to search */
    int comp = 1;                    /* the arr[0] check below counts as comparison #1 */
    if (arr[0] == target) { *comparisons = comp; return 0; }
    int bound = 1;
    while (bound < n) {                 /* double the bound until it overshoots target */
        comp++;
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    while (lo <= hi) {                  /* ordinary binary search inside [lo..hi] */
        int mid = lo + (hi - lo) / 2;
        comp++;
        if (arr[mid] == target) { *comparisons = comp; return mid; }
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    *comparisons = comp;
    return -1;
}

static int exponentialSearch(int[] arr, int target) {
    int n = arr.length;
    if (n <= 0) { comparisons = 0; return -1; }  // nothing to search
    comparisons = 1;                 // the arr[0] check below counts as comparison #1
    if (arr[0] == target) return 0;
    int bound = 1;
    while (bound < n) {                 // double the bound until it overshoots target
        comparisons++;
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    while (lo <= hi) {                  // ordinary binary search inside [lo..hi]
        int mid = lo + (hi - lo) / 2;
        comparisons++;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

In the picker, also try target near the end, the bound doubles several times (hard) and the edge cases target is the first element: a single comparison, target is larger than the last element, and target is in range but not in the array — or press 🎲 for random data, or type your own sorted array.

4.4 Try it¶

/* Week 6 -- Search and Hashing
 * Exponential search: on a SORTED array, double a bound (1, 2, 4, 8, ...)
 * until it overshoots target, then run ordinary binary search inside
 * [bound/2, bound]. Prints the bound-finding phase and the binary-search
 * phase.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

int exponential_search(const int arr[], int n, int target, int *comparisons) {
    if (n <= 0) { *comparisons = 0; return -1; }    /* nothing to search */
    int comp = 1;                    /* the arr[0] check below counts as comparison #1 */
    printf("  check arr[0] = %d\n", arr[0]);
    if (arr[0] == target) { *comparisons = comp; return 0; }
    int bound = 1;
    while (bound < n) {                 /* double the bound until it overshoots target */
        comp++;
        printf("  bound = %d: check arr[%d] = %d\n", bound, bound, arr[bound]);
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    printf("  binary search inside [%d..%d]\n", lo, hi);
    while (lo <= hi) {                  /* ordinary binary search inside [lo..hi] */
        int mid = lo + (hi - lo) / 2;
        comp++;
        printf("  compare arr[%d] = %d\n", mid, arr[mid]);
        if (arr[mid] == target) { *comparisons = comp; return mid; }
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    *comparisons = comp;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int comparisons = 0;
    int index = exponential_search(arr, n, target, &comparisons);
    if (index == -1) printf("result: not found, %d comparisons\n\n", comparisons);
    else printf("result: found at index %d, %d comparisons\n\n", index, comparisons);
}

int main(void) {
    int a[] = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63};
    int n = 16;

    run_scenario("normal: 16 values, target found around the middle", a, n, 39);
    run_scenario("hard: target near the end, the bound doubles several times", a, n, 59);
    run_scenario("edge: target is the first element, a single comparison", a, n, 3);
    run_scenario("edge: target is larger than the last element", a, n, 999);
    run_scenario("edge: target is in range but not in the array", a, n, 40);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Exponential search: on a SORTED array, double a bound (1, 2, 4, 8, ...)
 * until it overshoots target, then run ordinary binary search inside
 * [bound/2, bound]. Prints the bound-finding phase and the binary-search
 * phase.
 * CEN207 Data Structures (formerly CE205)
 */
public class ExponentialSearch {
    static int comparisons;

    static int exponentialSearch(int[] arr, int target) {
        int n = arr.length;
        if (n <= 0) { comparisons = 0; return -1; }  // nothing to search
        comparisons = 1;                 // the arr[0] check below counts as comparison #1
        System.out.println("  check arr[0] = " + arr[0]);
        if (arr[0] == target) return 0;
        int bound = 1;
        while (bound < n) {                 // double the bound until it overshoots target
            comparisons++;
            System.out.println("  bound = " + bound + ": check arr[" + bound + "] = " + arr[bound]);
            if (arr[bound] >= target) break;
            bound *= 2;
        }
        int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
        System.out.println("  binary search inside [" + lo + ".." + hi + "]");
        while (lo <= hi) {                  // ordinary binary search inside [lo..hi]
            int mid = lo + (hi - lo) / 2;
            comparisons++;
            System.out.println("  compare arr[" + mid + "] = " + arr[mid]);
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = exponentialSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + comparisons + " comparisons");
        else System.out.println("result: found at index " + index + ", " + comparisons + " comparisons");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63};

        runScenario("normal: 16 values, target found around the middle", a, 39);
        runScenario("hard: target near the end, the bound doubles several times", a, 59);
        runScenario("edge: target is the first element, a single comparison", a, 3);
        runScenario("edge: target is larger than the last element", a, 999);
        runScenario("edge: target is in range but not in the array", a, 40);
    }
}

Try it

gcc -std=c11 -Wall -Wextra -o /tmp/x exponential_search.c && /tmp/x

-- normal: 16 values, target found around the middle --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 39
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[9] = 39
result: found at index 9, 7 comparisons

-- hard: target near the end, the bound doubles several times --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 59
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[13] = 55
  compare arr[14] = 59
result: found at index 14, 8 comparisons

-- edge: target is the first element, a single comparison --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 3
  check arr[0] = 3
result: found at index 0, 1 comparisons

-- edge: target is larger than the last element --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 999
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[13] = 55
  compare arr[14] = 59
  compare arr[15] = 63
result: not found, 9 comparisons

-- edge: target is in range but not in the array --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 40
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[9] = 39
  compare arr[10] = 43
result: not found, 8 comparisons

javac -Xlint:all -d /tmp/j ExponentialSearch.java && java -cp /tmp/j ExponentialSearch

4.5 Complexity, mistakes, self-check¶

Complexity. O(log index) to find the bound, where index is the target's actual position (or n if absent) — not O(log n). The binary-search phase then costs O(log(bound)), where bound is at most 2 * index. Combined: O(log index) overall. When the target is near the front, this beats plain binary search's O(log n); when the target is near the end, the two become asymptotically the same.

5. Fibonacci search¶

5.1 A question to start¶

Binary search's midpoint computation, lo + (hi - lo) / 2, needs a division. On computing hardware from the 1950s and 1960s — and still today on some very constrained embedded processors — division is dramatically more expensive than addition or subtraction. Is there a way to get binary search's O(log n) guarantee using only addition and subtraction? Fibonacci search answers yes, by splitting the search range according to Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, …) instead of always splitting it exactly in half.

The technique traces back to work by the American statistician Jack Kiefer, whose 1953 paper Sequential Minimax Search for a Maximum used Fibonacci numbers to design an optimal strategy for a related problem (finding the maximum of a function using as few evaluations as possible); the same Fibonacci-number splitting idea was later adapted into a division-free search algorithm for sorted arrays, which is what you are learning here.

5.2 The idea¶

Find the smallest Fibonacci number fib that is >= n, together with the two Fibonacci numbers just before it, fib1 and fib2 (so fib = fib1 + fib2). Maintain an offset (initially -1) marking how far into the array the search has already eliminated. At each step, probe index i = offset + fib2 (clamped to n - 1 if that would overshoot). If arr[i] < target, the entire left part up to i is eliminated, offset moves to i, and the Fibonacci triple shrinks by one step (fib, fib1, fib2 = fib1, fib2, fib1 - fib2). If arr[i] > target, the right part is eliminated instead, and the triple shrinks by two steps (fib, fib1, fib2 = fib2, fib1 - fib2, fib - (fib1 - fib2)). Because Fibonacci numbers satisfy fib = fib1 + fib2 exactly, every one of these updates uses only addition and subtraction — never a division or a multiplication.

5.3 In memory, and the code¶

int fibonacci_search(const int arr[], int n, int target, int *comparisons) {
    int fib2 = 0, fib1 = 1, fib = fib1 + fib2;      /* smallest Fibonacci number >= n */
    while (fib < n) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; }
    int offset = -1, comp = 0;
    while (fib > 1) {
        int i = (offset + fib2 < n - 1) ? offset + fib2 : n - 1;
        comp++;
        if (arr[i] < target) {                       /* eliminate the left part */
            fib = fib1; fib1 = fib2; fib2 = fib - fib1;
            offset = i;
        } else if (arr[i] > target) {                /* eliminate the right part */
            fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1;
        } else {
            *comparisons = comp;
            return i;
        }
    }
    if (fib1 == 1 && offset + 1 < n) {                /* one element may be left over */
        comp++;
        if (arr[offset + 1] == target) { *comparisons = comp; return offset + 1; }
    }
    *comparisons = comp;
    return -1;
}

static int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    int fib2 = 0, fib1 = 1, fib = fib1 + fib2;      // smallest Fibonacci number >= n
    while (fib < n) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; }
    int offset = -1;
    comparisons = 0;
    while (fib > 1) {
        int i = (offset + fib2 < n - 1) ? offset + fib2 : n - 1;
        comparisons++;
        if (arr[i] < target) {                       // eliminate the left part
            fib = fib1; fib1 = fib2; fib2 = fib - fib1;
            offset = i;
        } else if (arr[i] > target) {                // eliminate the right part
            fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1;
        } else {
            return i;
        }
    }
    if (fib1 == 1 && offset + 1 < n) {                // one element may be left over
        comparisons++;
        if (arr[offset + 1] == target) return offset + 1;
    }
    return -1;
}