Searching and Hashing

Binary Search

This works only on a sorted array. Each step halves the search space, so it takes O(log n).

#include <stdio.h>
int binarySearch(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // avoids overflow
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
int main() {
    int a[] = {3, 8, 15, 23, 42, 56, 77};
    printf("42 found at index %d\n", binarySearch(a, 7, 42));
    printf("10 found at index %d\n", binarySearch(a, 7, 10));
}

42 found at index 4 10 found at index -1

	Linear search	Binary search
Requires sorted data	No	Yes
Time	O(n)	O(log n)

Hashing

A hash function maps a key to a table index. Example: h(k) = k mod 10. When two keys map to the same index, it's a collision.

Collision Resolution

Chaining: each slot holds a linked list.
Linear probing: try h(k)+1, h(k)+2, …
Quadratic probing: try h(k)+1², h(k)+2², …
Double hashing: try h1(k) + i·h2(k).

Text

Insert 23, 43, 13, 27 into a table of size 10 with h(k) = k mod 10, linear probing:
23 → 3
43 → 3 (taken) → 4
13 → 3 → 4 → 5
27 → 7
Index: 0 1 2 3  4  5  6 7  8 9
       - - - 23 43 13 - 27 - -

Load factor α = n / table size. Performance drops as α approaches 1.

Track your progress through the Data Structures course

← Prev