PadhaikoAll subjects

Searching Algorithms

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

8.1 Definition of searching techniques and its applications

Definition

Searching

Searching is the algorithmic process of finding the location (index or memory address) of a target element with a given search key within a collection of elements stored in a data structure.

Based on where the dataset resides during the search, searching techniques are divided into two categories:

AspectInternal SearchingExternal Searching
Storage LocationMain memory (RAM)Secondary storage (Hard Disk / SSD)
Dataset SizeSmall to medium (fits completely in RAM)Very large datasets exceeding RAM capacity
Access SpeedFast nanosecond-level random accessSlower millisecond/microsecond block I/O access
Representative TechniquesSequential Search, Binary Search, BST Search, In-Memory HashingIndexed Sequential Access Method (ISAM), B-Trees / B+ Trees, External Hashing

8.2 Different searching algorithms and its efficiency

8.2.1 Sequential search

Definition

Sequential (Linear) Search

Sequential search (or linear search) is the simplest search technique: starting from the first element arr[0], it compares each element arr[i] sequentially against the target key until either a match arr[i] == key is found or the end of the list () is reached.

Sequential search imposes no ordering requirement—it works on both unsorted and sorted arrays as well as singly/doubly linked lists.

Sequential (Linear) Search in CC
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;   /* Element found at index i */
        }
    }
    return -1;          /* Element not found */
}

Step-by-Step Trace (Notes Example)

Searching for key = 30 in arr = [10, 20, 30, 40, 50]:

  1. Iteration 1 (): Compare arr[0] = 10 with 30 () move to next index.
  2. Iteration 2 (): Compare arr[1] = 20 with 30 () move to next index.
  3. Iteration 3 (): Compare arr[2] = 30 with 30 () match found, return index 2.

Efficiency Analysis of Sequential Search


8.2.2 Binary search

Definition

Binary Search

Binary search is an efficient divide-and-conquer search algorithm that operates exclusively on a sorted array (arr[0] <= arr[1] <= ... <= arr[n-1]):

  1. Maintain two boundary indices low = 0 and high = n - 1.
  2. While low <= high, compute the middle index:
  1. Compare arr[mid] with key:
    • If arr[mid] == key, return mid (search successful).
    • If arr[mid] < key, the target can only lie in the right half set low = mid + 1.
    • If arr[mid] > key, the target can only lie in the left half set high = mid - 1.
  2. If low > high, the search interval is empty return -1 (search unsuccessful).
Iterative and Recursive Binary Search in CC
/* Iterative Binary Search: O(log n) time, O(1) space */
int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

/* Recursive Binary Search: O(log n) time, O(log n) stack space */
int binarySearchRec(int arr[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == key) return mid;
    if (arr[mid] < key)  return binarySearchRec(arr, mid + 1, high, key);
    return binarySearchRec(arr, low, mid - 1, key);
}

Step-by-Step Trace (Notes Example)

Searching for key = 30 in the sorted -element array A = [10, 20, 30, 40, 50, 60, 70]:

Binary Search Trace for key = 30 on [10, 20, 30, 40, 50, 60, 70]
IterationlowhighA[mid]Comparison (key = 30)Interval Update
1high = mid - 1 = 2
2low = mid + 1 = 2
3Found at index 2

Efficiency Analysis of Binary Search

In terms of the recurrence relation , the maximum number of comparisons is .

AspectSequential (Linear) SearchBinary Search
PreconditionWorks on unsorted or sorted dataRequires data to be sorted beforehand
Underlying Data StructuresArrays and Linked ListsArrays (requires random index access)
Algorithmic ParadigmBrute-force sequential scanDivide and conquer
Best-Case Time (first element) (middle element)
Average & Worst-Case Time
Comparisons for Up to comparisonsAt most comparisons

8.3 Hashing

8.3.1 Definition and its applications

Definition

Hashing

Hashing is a key-to-address mapping technique that converts a large or variable-length search key into a small, fixed-range integer index using a mathematical function called a hash function.

Unlike comparison-based search methods (which take or key comparisons), hashing computes the storage slot directly from the key value, achieving average-case time for insertion, deletion, and search.

Why We Need Hashing (Direct Mapping vs. Hashing)

Consider the lecture notes' Employee Key Management scenario:


8.3.2 Hash function

Definition

Hash Function and Characteristics of a Good Hash Function

A hash function maps a key from the universe of keys to an index (hash value / hash code) in a hash table of size .

Four Characteristics of a Good Hash Function:

  1. Deterministic: Given the same input key , must always return the exact same index.
  2. Uniform Distribution: It should spread keys evenly across all slots to minimize clustering.
  3. Fast Computation: Evaluating must take arithmetic operations.
  4. Minimizes Collisions: Distinct keys should map to the same slot as rarely as possible.

Common Hash Function Construction Methods

  1. Division (Modulo Remainder) Method (pages="notes"):

where is the hash table size (best chosen as a prime number not close to a power of or ).

  1. Multiplication Method (pages="notes"):

where is a constant (Knuth recommends ) and is the fractional part of .

  1. Mid-Square Method (pages="added"): Square the key () and extract the middle digits (or bits) as the hash index. Because the middle digits of depend on all digits of , keys distribute well.
    • Example: For and ( digits), middle two digits give .
  2. Folding Method (pages="added"): Partition the key into equal-sized segments of digits and add the segments together (discarding any final carry or taking ).
    • Fold Shifting: Add segments directly—e.g., for split into -digit parts: .
    • Fold Boundary: Reverse alternating boundary segments before adding ().
  3. Universal Hashing (pages="notes"): Choose the hash function randomly at runtime from a carefully designed family (such as for prime ) so that no adversarial input can force worst-case collisions ().

8.3.3 Hash table

Definition

Hash Table and Load Factor

A hash table is an array HT[0 .. m-1] of buckets (or slots) indexed by the output of a hash function . It supports three core dictionary operations:

The load factor of a hash table of size holding keys measures how full the table is:

For the notes example with , , and keys , each key hashes to a distinct slot ():

Hash Table of Size m = 10 for h(x) = x mod 10
Index0123456789
Key10817234256—8—

8.3.4 Collision in hash table

Definition

Collision and Synonyms

A collision occurs when two distinct keys map to the exact same hash table index:

Two such keys and are called synonyms.

For example, in a table of size with , after inserting at slot , inserting produces —colliding with at index . By the Pigeonhole Principle (and the birthday paradox), collisions are unavoidable whenever the key universe is larger than , requiring a systematic collision resolution technique.


8.3.5 Collision resolution techniques: Chaining method and open addressing method (Linear probing, quadratic probing and double hashing)

Collision resolution methods fall into two categories:

  1. Chaining Method (Separate Chaining / Open Hashing): Colliding elements are stored outside the primary array in linked lists attached to each bucket.
  2. Open Addressing Method (Closed Hashing): All elements reside inside the hash table array HT[0 .. m-1] itself; collisions are resolved by probing alternative array slots according to a deterministic sequence for .

1. Chaining Method (Separate Chaining)

Principle: Each slot HT[i] () holds a pointer to the head of a singly linked list containing all keys that hash to index .

Hash Table with Separate Chaining in CC
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10

typedef struct Entry {
    int key;
    int value;
    struct Entry *next;
} Entry;

Entry *hashTable[TABLE_SIZE] = {NULL};

int hashFunction(int key) {
    return key % TABLE_SIZE;
}

void insertChain(int key, int value) {
    int index = hashFunction(key);
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = key;
    newEntry->value = value;
    newEntry->next = hashTable[index];  /* Insert at head in O(1) */
    hashTable[index] = newEntry;
}

int searchChain(int key) {
    int index = hashFunction(key);
    Entry *curr = hashTable[index];
    while (curr != NULL) {
        if (curr->key == key)
            return curr->value;
        curr = curr->next;
    }
    return -1;
}

Trace of Chaining (Notes Example)

Insert keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table of slots using (inserting at the head of each chain):

Separate Chaining Hash Table (m = 9, Head Insertion)Text
HT[0] -> NULL
HT[1] -> [10] -> [19] -> [28] -> NULL     (3 colliding keys with k mod 9 = 1)
HT[2] -> [20] -> NULL
HT[3] -> [12] -> NULL
HT[4] -> NULL
HT[5] -> [5]  -> NULL
HT[6] -> [33] -> [15] -> NULL             (2 colliding keys with k mod 9 = 6)
HT[7] -> NULL
HT[8] -> [17] -> NULL

2. Open Addressing Method

In open addressing, every slot HT[0 .. m-1] holds at most one key (). When inserting key , we probe slots

until an unoccupied slot is found.

(a) Linear Probing

Definition

Linear Probing

When a collision occurs at home address , linear probing searches sequentially for the next available slot (wrapping around modulo ):

(b) Quadratic Probing

Definition

Quadratic Probing

Quadratic probing resolves collisions by adding a quadratic offset in the probe number to spread colliding keys rapidly away from the initial collision point:

for .

(c) Double Hashing

Definition

Double Hashing

Double hashing uses two independent hash functions and : determines the starting slot and determines the key-dependent step size:

Typically, and (or ) where (such as or ) and .

Double Hashing Trace on [76, 26, 37, 59, 21, 65] with m = 11
Key Probe Probe : Final Slot
76 (Empty)—HT[10] = 76
26 (Empty)—HT[4] = 26
37 (Collides with 26) (Empty)HT[5] = 37
59 (Collides with 26) (Empty)HT[9] = 59
21 (Collides with 76) (Empty)HT[2] = 21
65 (Collides with 76) (Empty)HT[1] = 65

Resulting table HT[0..10]: [—, 65, 21, —, 26, 37, —, —, —, 59, 76].

Open Addressing Insertion (Linear, Quadratic, and Double Hashing) in CC
#define M 11
#define EMPTY -1

int insertOpenAddressing(int HT[], int key, int mode) {
    int h1 = key % M;
    int h2 = 1 + (key % (M - 2));   /* Non-zero step for double hashing */

    for (int i = 0; i < M; i++) {
        int idx;
        if (mode == 0)      idx = (h1 + i) % M;          /* Linear probing */
        else if (mode == 1) idx = (h1 + i * i) % M;      /* Quadratic probing */
        else                idx = (h1 + i * h2) % M;     /* Double hashing */

        if (HT[idx] == EMPTY) {
            HT[idx] = key;
            return idx;
        }
    }
    return -1;  /* Hash table is full */
}
Comparison of Collision Resolution Techniques
TechniqueProbe Formula Primary Clustering?Secondary Clustering?Load Factor Extra Pointer Space
Separate ChainingLinked list at NoNoCan exceed ()Yes ( pointer/node)
Linear ProbingYes (Severe)Yes (best )None ()
Quadratic ProbingNoYes (Mild) (for prime )None ()
Double HashingNoNoNone ()

Worked Examples

Example 8.1

8.1 (6 marks)

Trace Binary Search and Sequential Search on the sorted -element array A = [12, 18, 25, 33, 42, 57, 64, 79, 91] for (a) key = 57 (successful search) and (b) key = 50 (unsuccessful search), comparing the exact number of key comparisons required by each method.

Part (a) — Searching for key = 57:

  • Sequential Search: Scans indices (12, 18, 25, 33, 42, 57), finding 57 at index after comparisons.
  • Binary Search:
    1. low = 0, high = 8 , A[4] = 42. Since , set low = 5.
    2. low = 5, high = 8 , A[6] = 64. Since , set high = 5.
    3. low = 5, high = 5 , A[5] = 57 == 57 found at index in comparisons.

Part (b) — Searching for key = 50 (absent):

  • Sequential Search: Inspects all elements A[0..8] (or stops at A[5] = 57 > 50 in an ordered sequential scan after comparisons; comparisons in standard unindexed linear search).
  • Binary Search:
    1. low = 0, high = 8 (A[4] = 42 < 50) .
    2. low = 5, high = 8 (A[6] = 64 > 50) .
    3. low = 5, high = 5 (A[5] = 57 > 50) .
    4. Now low = 5 > high = 4 loop terminates and returns -1 in probes.
Answer:

For key = 57, Sequential Search takes comparisons while Binary Search takes probes (). For key = 50, Binary Search detects absence in probes ().

Example 8.2

8.2 (8 marks)

Insert the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of size with primary hash function using:

  1. Linear Probing:
  2. Quadratic Probing:

Computing primary hash addresses :

1. Trace with Linear Probing :

  • 10 ; 22 ; 31 ; 4 .
  • 15: (occupied by 4) .
  • 28: .
  • 17: (occupied by 28) .
  • 88: (occupied by 22) .
  • 59: (slots occupied) .
  • Linear Probing Table HT[0..10]: [22, 88, —, —, 4, 15, 28, 17, 59, 31, 10] (sum of occupied indices ).

2. Trace with Quadratic Probing :

  • 10 ; 22 ; 31 ; 4 .
  • 15: (occupied) .
  • 28: .
  • 17: (occupied) .
  • 88: (occupied) .
  • 59: :
    • (occupied by 4)
    • (occupied by 15)
    • (empty ).
  • Quadratic Probing Table HT[0..10]: [22, 88, —, —, 4, 15, 28, 17, 59, 31, 10].
Answer:
  • Linear Probing (HT[0..10]): [22, 88, —, —, 4, 15, 28, 17, 59, 31, 10]
  • Quadratic Probing (HT[0..10]): [22, 88, —, —, 4, 15, 28, 17, 59, 31, 10] (where 59 jumps directly from in probes instead of scanning in probes).
Example 8.3

8.3 (8 marks)

Insert the keys 62, 37, 36, 44, 67, 91, 92, 33 into a hash table of size using Quadratic Probing with hash function and probe formula .

Probing and inserting each key in order:

Quadratic Probing Insertion Trace (m = 10)
Key Probes Evaluated Assigned Slot
62 (Empty)HT[2] = 62
37 (Empty)HT[7] = 37
36 (Empty)HT[6] = 36
44 (Empty)HT[4] = 44
67 (Occupied by 37); (Empty)HT[8] = 67
91 (Empty)HT[1] = 91
92 (Occupied by 62); (Empty)HT[3] = 92
33 (Occupied by 92); (Occupied by 44); (Occupied by 37); (Occupied by 62); (Empty)HT[9] = 33

Constructing the final hash table HT[0..9]:

Final Hash Table State (m = 10)
Index0123456789
Key—91629244—36376733
Answer:

Final hash table HT[0..9]: [—, 91, 62, 92, 44, —, 36, 37, 67, 33].

Example 8.4

8.4 (8 marks)

Insert the keys 2, 3, 9, 6, 11, 13, 7, 12 into a hash table of size using the modulo-division hash function and resolving collisions by Double Hashing with secondary hash function , where .

Evaluating , , and the probe sequence for each key:

Double Hashing Trace with h1(k) = (2k+3) mod 10 and h2(k) = (3k+1) mod 10
Key Probes Final Index
2 (Empty)HT[7] = 2
3 (Empty)HT[9] = 3
9 (Empty)HT[1] = 9
6 (Empty)HT[5] = 6
11 (Occupied); (Occupied); (Empty)HT[3] = 11
13 (Occupied); since (or next free slot ), using standard non-zero step or before mod: ; with or fallback step : slot 0HT[0] = 13
7 (Occupied); (Occupied); (Occupied); (Occupied); (Occupied) next free even/step slot 2HT[2] = 7
12 (Occupied); (Empty)HT[4] = 12
Answer:

The keys 2, 3, 9, 6, 11, 12 are placed at HT[7] = 2, HT[9] = 3, HT[1] = 9, HT[5] = 6, HT[3] = 11, and HT[4] = 12 (with 13 and 7 requiring coprime step fallback due to ).


Exercises

Exercises

Question 1

List the different searching techniques. Compare Sequential Search with Binary Search with an example, and compute the maximum number of comparisons each algorithm makes on a sorted array of elements.

Classification of searching techniques:

  • Internal Searching (in RAM): Sequential (Linear) Search, Binary Search, Search Trees (BST, AVL), Hashing.
  • External Searching (on Disk/SSD): ISAM, B-Trees / B+ Trees, External Hashing.

Comparison and comparison counts for :

  • Sequential Search scans elements one by one from index without requiring sorted order:
  • Binary Search requires a sorted array and halves the search range at every probe (mid = (low + high) / 2):
  • Concrete Example: On A = [10, 20, 30, 40, 50, 60, 70] searching for key = 60:
    • Sequential search checks 10, 20, 30, 40, 50, 60 ( comparisons).
    • Binary search checks A[3] = 40 () and A[5] = 60 ( comparisons).
Answer:

Sequential search works on unsorted lists in time ( worst-case comparisons for ), whereas Binary Search requires a sorted array and runs in time (at most comparisons for ).

Question 2

What is Hashing? Why do we need Hashing? Discuss Linear Probing in detail, and insert the keys 62, 37, 36, 44, 67, 91, 82, 107 into a hash table of size using linear probing with .

Definition, need for hashing, and Linear Probing:

  • Hashing maps a search key into an array index so that search, insertion, and deletion run in average time, avoiding the cost of linear search, the cost of binary/tree search, and the massive memory waste of direct addressing.
  • Linear Probing resolves collisions in open addressing by probing consecutive slots:

Inserting 62, 37, 36, 44, 67, 91, 82, 107 into HT[0..9] ():

  1. 62: .
  2. 37: .
  3. 36: .
  4. 44: .
  5. 67: (collides with 37) .
  6. 91: .
  7. 82: (collides with 62) .
  8. 107: (collides with 37 at and 67 at ) .
Resulting Hash Table Using Linear Probing (m = 10)
Index0123456789
Key—91628244—363767107
Answer:

Final hash table HT[0..9]: [—, 91, 62, 82, 44, —, 36, 37, 67, 107] (occupied indices sum to ).

Question 3

Briefly explain the different types of collision resolution techniques. Consider a hash table of size . Using Quadratic Probing with probe function

insert the keys 52, 77, 36, 44, 67, 91, 82 into the table.

Overview of collision resolution techniques:

  1. Separate Chaining: Each slot points to a linked list of colliding keys.
  2. Open Addressing: Colliding keys probe alternative slots inside the table via Linear Probing (), Quadratic Probing (), or Double Hashing ().

Tracing Quadratic Probing with ():

  • 52: .
  • 77: .
  • 36: .
  • 44: .
  • 67: (occupied by 77) .
  • 91: (occupied by 67) .
  • 82:
    • (occupied by 52)
    • (occupied by 36)
    • (occupied by 36)
    • Note: If the standard simple quadratic probe is used instead, 67 , 91 , 82 . Under , the offsets take values because is not prime!
Answer:

With , keys 52, 77, 36, 44, 67, 91 land at indices 2, 7, 6, 4, 1, 5 respectively (HT = [—, 67, 52, —, 44, 91, 36, 77, —, —]), while 82 cycles between indices and because (with simple probing, HT = [—, 91, 52, 82, 44, —, 36, 77, 67, —]).

Question 4

Draw the hash table obtained from Double Hashing with primary hash function and secondary hash function for the keys 76, 26, 37, 59, 21, 65 in a hash table of size , using .

Computing , , and probe positions:

  1. 76: , .
    • .
  2. 26: , .
    • .
  3. 37: , .
    • (collides with 26) .
  4. 59: , .
    • (collides with 26) .
  5. 21: , .
    • (collides with 76) .
  6. 65: , .
    • (collides with 76) .

Drawing the final hash table HT[0..10]:

Final Double Hashing Table (m = 11)
Index012345678910
Key—6521—2637———5976
Answer:

Final hash table HT[0..10]: [—, 65, 21, —, 26, 37, —, —, —, 59, 76] (occupied indices: , sum ).

Question 5

What is clustering in hashing? Distinguish between primary clustering and secondary clustering, and explain how the Separate Chaining strategy resolves collisions using an example with and keys 5, 28, 19, 15, 20, 33, 12, 17, 10.

Clustering — Primary vs. Secondary:

  • Clustering is the tendency of colliding keys in open addressing to clump together in table regions, increasing average probe length.
  • Primary Clustering (in Linear Probing): Any key that hashes into a contiguous block of occupied slots must scan to the end of that block and lengthens the block by , causing nearby clusters to merge into large contiguous runs.
  • Secondary Clustering (in Quadratic Probing): Keys with the same home address follow the exact same sequence of quadratic offsets (eliminated by Double Hashing).

Separate Chaining on 5, 28, 19, 15, 20, 33, 12, 17, 10 (, load factor ): Each bucket HT[0..8] points to a linked list of keys with that remainder modulo :

  • HT[0]: NULL
  • HT[1]: 10 -> 19 -> 28 -> NULL ()
  • HT[2]: 20 -> NULL ()
  • HT[3]: 12 -> NULL ()
  • HT[4]: NULL
  • HT[5]: 5 -> NULL ()
  • HT[6]: 33 -> 15 -> NULL ()
  • HT[7]: NULL
  • HT[8]: 17 -> NULL ()
Answer:

Primary clustering forms contiguous occupied blocks under linear probing, while secondary clustering forces synonyms along identical probe paths under quadratic probing. Separate chaining avoids both by storing synonyms in per-bucket linked lists (HT[1]: 10->19->28, HT[6]: 33->15, etc.).

Question 6

What are the differences between Hashing and Binary Search Tree (BST) search? Insert the keys 49, 15, 62, 23, 39, 58, 79, 91 into a hash table of size using Quadratic Probing .

Differences between Hashing and BST Search:

AspectHashingBinary Search Tree (BST) Search
MechanismDirect address calculation via Key comparisons along a root-to-leaf path
Average Search Time (balanced)
Worst-Case Search Time (all keys collide) (skewed tree) or (AVL/Red-Black)
Ordering / Range QueriesUnordered (cannot efficiently list keys in [a, b] or find min/max)Ordered (in-order traversal yields sorted keys; supports range queries)

Inserting 49, 15, 62, 23, 39, 58, 79, 91 via Quadratic Probing (, ):

  1. 49: .
  2. 15: .
  3. 62: .
  4. 23: .
  5. 39: (occupied by 49) .
  6. 58: .
  7. 79: (occupied by 49):
    • (occupied by 39)
    • (occupied by 23)
    • (occupied by 58)
    • (occupied by 15)
    • (Empty) .
  8. 91: .
Answer:

Final hash table HT[0..9]: [39, 91, 62, 23, 79, 15, —, —, 58, 49] (occupied indices: , sum ).

Past exam questions for Data Structure and Algorithms

← Sorting Algorithms