Unit VIII: Searching (5 Hrs.)

Data Structures & Algorithms — Complete Detailed Chapter Notes

Every technique includes: detailed concept · pseudocode · step-form algorithm · at least two fully-traced examples (with tables/diagrams) · best-case & worst-case analysis · complete clean Java code · complexity. Ends with fully-answered important questions (2 / 6 / 10 marks).

Table of Contents

  1. Introduction
  2. Searching Techniques
  3. Hashing
  4. Collision Resolution Techniques
  5. Hashing with Open Addressing
  6. Hashing with Chaining
  7. Rehashing
  8. Efficiency Comparison of Search Techniques
  9. Important Questions with Full Answers

8.1 Introduction

Searching is the process of finding the location (index/position) of a particular element — called the target or search key — within a collection of data, or determining that the element is not present.

Searching is one of the most frequently performed operations in computing, because stored data is only useful if we can retrieve specific items from it quickly. Examples include finding a contact in a phone book, looking up a word in a dictionary, or a database locating a customer record.

Classification of searching techniques

Searching methods fall into two broad families:

  1. Comparison-based searching — the key is compared against elements of the data structure until a match is found.

    • Sequential (Linear) Search — checks elements one by one.
    • Binary Search — repeatedly halves a sorted search space.
    • Tree Search — navigates a Binary Search Tree.

  2. Computed-address (hash-based) searching — the position of the key is computed directly using a hash function, giving average O(1) access without scanning.

    • Hashing with collision resolution.

Two key factors that decide which method to use

  • Is the data sorted? Binary Search needs sorted data; Linear Search does not.
  • What is the data structure? Arrays favor linear/binary search; trees favor tree search; hash tables favor hashing.
                        SEARCHING
              ┌──────────────┴───────────────┐
       Comparison-based                Hash-based
        ┌──────┼───────┐                   │
     Linear  Binary   Tree              Hashing
     Search  Search  Search        (O(1) average lookup)

8.2 Searching Techniques

8.2.1 Sequential (Linear) Search

Concept (detailed)

Sequential Search (also called Linear Search) is the simplest searching technique. It examines each element of the list one by one, from the beginning to the end, comparing it with the target key. If a match is found, it returns the position; if the end of the list is reached without a match, it reports "not found." It works on both sorted and unsorted data and needs no preprocessing, which is its main strength.

Pseudocode

function LINEAR_SEARCH(A, n, key)
    for i ← 0 to n-1 do
        if A[i] = key then
            return i          // found at index i
        end if
    end for
    return -1                 // not found
end function

Algorithm (step form)

  1. Start from the first element (index 0).
  2. Compare the current element with the key.
  3. If they are equal, return the current index (search successful).
  4. If not, move to the next element.
  5. Repeat until the element is found or the list ends.
  6. If the list ends with no match, return −1 (search unsuccessful).

Example 1 (successful search) — A = [45, 12, 78, 23, 9, 56], key = 23

i A[i] A[i] == 23 ? Result
0 45 No continue
1 12 No continue
2 78 No continue
3 23 Yes found at index 3

Output: Element 23 found at index 3 (4 comparisons).

Example 2 (unsuccessful search) — A = [10, 20, 30, 40, 50], key = 90

i A[i] A[i] == 90 ? Result
0 10 No continue
1 20 No continue
2 30 No continue
3 40 No continue
4 50 No end reached

Output: 90 not found → return −1 (5 comparisons — the full list scanned).

Best Case & Worst Case

  • Best case: the key is the first element → 1 comparison → O(1).
  • Worst case: the key is the last element or absent → n comparisons → O(n).
  • Average case: about n/2 comparisons → O(n).

Java Code

public class LinearSearch {
    static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {      // match found
                return i;
            }
        }
        return -1;                    // not found
    }

    public static void main(String[] args) {
        int[] arr = {45, 12, 78, 23, 9, 56};
        int key = 23;
        int index = linearSearch(arr, key);
        if (index != -1)
            System.out.println(key + " found at index " + index);
        else
            System.out.println(key + " not found");
    }
}

Complexity Summary

Case Comparisons Time Space
Best 1 O(1) O(1)
Average n/2 O(n) O(1)
Worst n O(n) O(1)

Advantages: Simple; works on unsorted data; no preprocessing. Disadvantages: Slow for large lists (O(n)).

8.2.2 Binary Search

Concept (detailed)

Binary Search is an efficient technique that works only on a sorted array. It uses a divide-and-conquer strategy: compare the key with the middle element.

  • If they are equal → element found.
  • If the key is smaller than the middle → search the left half.
  • If the key is larger than the middle → search the right half.

Each comparison halves the remaining search space, so the number of comparisons grows only logarithmically — O(log n). For 1,000,000 elements, Binary Search needs at most ~20 comparisons, whereas Linear Search may need 1,000,000.

Pseudocode (iterative)

function BINARY_SEARCH(A, n, key)
    low ← 0
    high ← n - 1
    while low ≤ high do
        mid ← (low + high) / 2
        if A[mid] = key then
            return mid
        else if A[mid] < key then
            low ← mid + 1        // search right half
        else
            high ← mid - 1       // search left half
        end if
    end while
    return -1                    // not found
end function

Algorithm (step form)

  1. Set low = 0 and high = n − 1.
  2. While low ≤ high: compute mid = (low + high) / 2.
  3. If A[mid] == key, return mid (found).
  4. If A[mid] < key, discard the left half by setting low = mid + 1.
  5. If A[mid] > key, discard the right half by setting high = mid − 1.
  6. If the loop ends (low > high), return −1 (not found).

Example 1 (successful) — A = [11, 22, 33, 44, 55, 66, 77], key = 55

Step low high mid A[mid] Comparison Action
1 0 6 3 44 44 < 55 low = 4
2 4 6 5 66 66 > 55 high = 4
3 4 4 4 55 55 == 55 found at index 4

Search-space visualization:

[11 22 33 44 55 66 77]   mid=44 → go right
             [55 66 77]   mid=66 → go left
             [55]         mid=55 → FOUND

Output: 55 found at index 4 (3 comparisons).

Example 2 (successful) — A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], key = 72

Step low high mid A[mid] Comparison Action
1 0 9 4 16 16 < 72 low = 5
2 5 9 7 56 56 < 72 low = 8
3 8 9 8 72 72 == 72 found at index 8

Output: 72 found at index 8 (3 comparisons).

Recursive Version (pseudocode + Java)

function BINARY_SEARCH_REC(A, low, high, key)
    if low > high then return -1
    mid ← (low + high) / 2
    if A[mid] = key then return mid
    if A[mid] < key then return BINARY_SEARCH_REC(A, mid+1, high, key)
    else return BINARY_SEARCH_REC(A, low, mid-1, key)
end function

Best Case & Worst Case

  • Best case: the key is at the middle → 1 comparison → O(1).
  • Worst case: the key is at an extreme or absent → the search space is halved until it becomes empty → about log₂n comparisons → O(log n).

Java Code (iterative + recursive)

public class BinarySearch {

    // Iterative
    static int binarySearch(int[] arr, int key) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;   // avoids integer overflow
            if (arr[mid] == key) return mid;
            else if (arr[mid] < key) low = mid + 1;  // right half
            else high = mid - 1;                     // left half
        }
        return -1;
    }

    // Recursive
    static 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);
    }

    public static void main(String[] args) {
        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        System.out.println("Iterative: index " + binarySearch(arr, 55));           // 4
        System.out.println("Recursive: index " + binarySearchRec(arr, 0, arr.length - 1, 55)); // 4
    }
}

Complexity Summary

Case Time Space
Best O(1) O(1) iterative
Average O(log n) O(1) iterative
Worst O(log n) O(log n) recursive

Requirement: data must be sorted. Advantages: Very fast (O(log n)) for large sorted data. Disadvantages: Requires sorted data; inefficient for frequently changing data (needs re-sorting); works best on arrays (random access), not linked lists.

8.2.3 Tree Search (BST)

Concept (detailed)

Tree Search operates on a Binary Search Tree (BST) — a binary tree with the ordering property that, for every node:

  • all keys in its left subtree are smaller than the node, and
  • all keys in its right subtree are larger than the node.

To search, start at the root and compare the key with the current node:

  • if equal → found;
  • if smaller → move to the left child;
  • if larger → move to the right child;
  • if you reach a null link → the key is not present.

Because each comparison discards one subtree, a balanced BST gives O(log n) search — similar to binary search, but on a dynamic structure that also supports fast insertion and deletion.

Sample BST (built from [50, 30, 70, 20, 40, 60, 80])

              50
           /      \
         30        70
        /  \      /  \
      20    40  60    80

Pseudocode

function TREE_SEARCH(node, key)
    if node = NULL then
        return NULL              // not found
    if key = node.data then
        return node              // found
    else if key < node.data then
        return TREE_SEARCH(node.left, key)
    else
        return TREE_SEARCH(node.right, key)
end function

Algorithm (step form)

  1. Start at the root node.
  2. If the node is null → key not found.
  3. If key equals the node's value → found.
  4. If key is smaller → repeat the search in the left subtree.
  5. If key is larger → repeat the search in the right subtree.

Example 1 (successful) — search 40 in the sample BST

Step Current node Comparison Move
1 50 40 < 50 go left
2 30 40 > 30 go right
3 40 40 == 40 found

Path visualization: 50 → 30 → 40 (3 comparisons).

Example 2 (unsuccessful) — search 65 in the sample BST

Step Current node Comparison Move
1 50 65 > 50 go right
2 70 65 < 70 go left
3 60 65 > 60 go right
4 null — not found

Path visualization: 50 → 70 → 60 → null → 65 not present.

Best Case & Worst Case

  • Best case: the key is at the root → 1 comparison → O(1).
  • Average case (balanced tree): height ≈ log n → O(log n).
  • Worst case (skewed tree): if the tree degenerates into a chain (e.g., keys inserted in sorted order), height = n → O(n). Self-balancing trees (AVL, Red-Black) guarantee O(log n).

Skewed (worst-case) tree from sorted input [10, 20, 30, 40]:

10
  \
   20
     \
      30
        \
         40      → search behaves like linear search: O(n)

Java Code

public class TreeSearch {
    static class Node {
        int data; Node left, right;
        Node(int d) { data = d; }
    }

    // Insert to build a BST
    static Node insert(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.data) root.left = insert(root.left, value);
        else root.right = insert(root.right, value);
        return root;
    }

    // Search a key
    static boolean search(Node root, int key) {
        if (root == null) return false;             // reached a null link
        if (key == root.data) return true;          // found
        return (key < root.data)
                ? search(root.left, key)            // go left
                : search(root.right, key);          // go right
    }

    public static void main(String[] args) {
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        Node root = null;
        for (int v : values) root = insert(root, v);

        System.out.println("Search 40: " + search(root, 40)); // true
        System.out.println("Search 65: " + search(root, 65)); // false
    }
}

Complexity Summary

Case Time Space
Best O(1) O(h) recursion
Average (balanced) O(log n) O(log n)
Worst (skewed) O(n) O(n)

Advantages: Dynamic — supports fast search, insert, and delete together; in-order traversal gives sorted order. Disadvantages: Degrades to O(n) if unbalanced; needs extra memory for pointers.

8.3 Hashing

Hashing is a technique that maps a key directly to a table index (address) using a hash function, so that data can be stored and retrieved in average O(1) time — without comparing against other elements.

   key ──► [ Hash Function h(key) ] ──► index ──► Hash Table[index] = value

The array that stores the values is called the hash table; the function that computes the index is the hash function; when two keys map to the same index, it is called a collision.

8.3.1 Hash Functions

A hash function h(key) transforms a key into a valid index in the range 0 … (m − 1), where m is the size of the hash table. The same key must always produce the same index.

Example: with table size m = 10 and h(k) = k mod 10:

  • h(23) = 23 mod 10 = 3 → store at index 3
  • h(56) = 56 mod 10 = 6 → store at index 6

8.3.2 Characteristics of a Good Hash Function

  1. Fast/easy to compute — computing the index should take constant time, O(1).
  2. Uniform distribution — keys should spread evenly across all slots to avoid clustering.
  3. Minimizes collisions — different keys should rarely map to the same index.
  4. Deterministic — the same key must always yield the same index.
  5. Uses the entire key — every part of the key should influence the result, reducing patterns.
  6. Low load sensitivity — should perform well as the table fills up (works with the load factor).

8.3.3 Types of Hash Functions

(a) Division Method

h(k) = k mod m, where m is the table size (best chosen as a prime number, not a power of 2).

  • Example 1: k = 1234, m = 97 → 1234 mod 97 = 70.
  • Example 2: k = 56, m = 10 → 56 mod 10 = 6.

(b) Mid-Square Method

Square the key, then take the middle digits of the result as the index.

  • Example: k = 1234 → 1234² = 1522756 → middle 3 digits = 227 → then 227 mod m.
  • Advantage: the middle digits depend on all digits of the key, giving good distribution.

(c) Folding Method

Split the key into equal-length parts, add them, and take mod m.

  • Example: k = 123456 → split into 12 | 34 | 56 → 12 + 34 + 56 = 102 → 102 mod 100 = 2.

(d) Multiplication Method

h(k) = floor(m × (k·A mod 1)), where 0 < A < 1 (Knuth suggests A ≈ 0.618).

  • Example: k = 123, m = 100, A = 0.618 → 123 × 0.618 = 76.014 → fractional part 0.014 → 100 × 0.014 = 1.4 → floor = 1.

8.3.4 Hash Tables and Applications

A hash table is an array-based data structure that stores key–value pairs at indices computed by a hash function, providing average O(1) insertion, deletion, and search.

Applications of hashing:

  1. Dictionaries / Maps / Sets — e.g., Java HashMap, HashSet, Python dict.
  2. Database indexing — fast lookup of records by key.
  3. Symbol tables in compilers — store identifiers and their attributes.
  4. Caching / Memoization — store computed results keyed by inputs.
  5. Password storage — store hash values instead of plain passwords.
  6. Detecting duplicates and spell checkers.
  7. Cryptography and file integrity — checksums, digital signatures.

8.4 Collision Resolution Techniques

A collision occurs when two different keys hash to the same index. Since each slot can normally hold only one entry, collisions must be resolved. There are two major strategies:

                Collision Resolution
             ┌────────────┴─────────────┐
      Open Addressing              Separate Chaining
     (store inside table)         (linked list per slot)
     ┌──────┼─────────┐
  Linear  Quadratic  Double
  Probing  Probing   Hashing
  1. Open Addressing (Closed Hashing): all elements are stored inside the table. On collision, the algorithm probes for the next free slot using a probe sequence — linear probing, quadratic probing, or double hashing.
  2. Separate Chaining (Open Hashing): each table slot points to a linked list that holds all keys hashing to that slot.

8.5 Hashing with Open Addressing

In open addressing, every element is stored within the array itself. When a collision happens, we search (probe) for an alternative empty slot according to a fixed rule.

Common setup for all three examples below: table size m = 10, base hash h(k) = k mod 10, and we insert the keys {23, 43, 13, 33} (all hash to index 3 → guaranteed collisions).

8.5.1 Linear Probing

Rule: on collision, check the next slot sequentially: index = (h(k) + i) mod m for i = 0, 1, 2, 3, …

Trace — insert {23, 43, 13, 33} (add 27 to show a separate index)

Key h(k) Probe sequence Placed at
23 3 slot 3 (empty) 3
43 3 3 occupied → 4 (empty) 4
13 3 3, 4 occupied → 5 (empty) 5
33 3 3, 4, 5 occupied → 6 (empty) 6
27 7 slot 7 (empty) 7

Resulting hash table:

Index:  0   1   2   3    4    5    6    7   8   9
Value:  -   -   -   23   43   13   33   27  -   -

Searching uses the same probe sequence: to find 33, compute 3, probe 3→4→5→6, found at 6.

Drawback — Primary Clustering: long continuous runs of filled slots form (indices 3–6 above), making later insertions and searches longer.

Java Code

import java.util.Arrays;

public class LinearProbing {
    int[] table; int size;

    LinearProbing(int size) {
        this.size = size;
        table = new int[size];
        Arrays.fill(table, -1);          // -1 marks empty
    }

    void insert(int key) {
        int idx = key % size;
        while (table[idx] != -1)         // probe next slot
            idx = (idx + 1) % size;
        table[idx] = key;
    }

    int search(int key) {
        int idx = key % size, start = idx;
        while (table[idx] != -1) {
            if (table[idx] == key) return idx;   // found
            idx = (idx + 1) % size;
            if (idx == start) break;             // looped fully
        }
        return -1;
    }

    public static void main(String[] args) {
        LinearProbing h = new LinearProbing(10);
        for (int k : new int[]{23, 43, 13, 33, 27}) h.insert(k);
        System.out.println(Arrays.toString(h.table));
        System.out.println("33 found at index " + h.search(33));  // 6
    }
}

8.5.2 Quadratic Probing

Rule: on collision, probe at quadratically increasing distances: index = (h(k) + i²) mod m for i = 0, 1, 2, 3, …

Trace — insert {23, 43, 13, 33}

Key h(k) Probe sequence (i = 0,1,2,3…) Placed at
23 3 (3+0)=3 empty 3
43 3 3 occupied → (3+1²)=4 empty 4
13 3 3, 4 occupied → (3+2²)=7 empty 7
33 3 3,4,7 occ → (3+3²)=12 mod 10=2 empty 2

Resulting hash table:

Index:  0   1   2    3    4   5   6   7    8   9
Value:  -   -   33   23   43  -   -   13   -   -

Advantage: avoids primary clustering (probes spread out). Drawback — Secondary Clustering: keys with the same initial index still follow the same probe path; also, some slots may never be probed unless m is prime and the table is less than half full.

8.5.3 Double Hashing

Rule: use a second hash function to compute the step size, so different keys follow different probe paths: index = (h1(k) + i · h2(k)) mod m for i = 0, 1, 2, …

A common choice: h1(k) = k mod m and h2(k) = R − (k mod R), where R is a prime smaller than m. Here take R = 7.

Trace — insert {23, 43, 13, 33}, h1 = k mod 10, h2 = 7 − (k mod 7)

Key h1 h2 = 7 − (k mod 7) Probe sequence Placed at
23 3 7−(23 mod 7)=7−2=5 (3) empty 3
43 3 7−(43 mod 7)=7−1=6 3 occ → (3+1·6)=9 empty 9
13 3 7−(13 mod 7)=7−6=1 3 occ → (3+1·1)=4 empty 4
33 3 7−(33 mod 7)=7−5=2 3 occ → (3+1·2)=5 empty 5

Resulting hash table:

Index:  0   1   2   3    4    5    6   7   8   9
Value:  -   -   -   23   13   33   -   -   -   43

Advantage: best distribution of the three methods; eliminates both primary and secondary clustering because the step size varies per key.

Comparison of Open-Addressing Methods

Method Probe formula Clustering Notes
Linear Probing (h(k) + i) mod m Primary Simplest; good cache locality
Quadratic Probing (h(k) + i²) mod m Secondary Reduces primary clustering
Double Hashing (h1(k) + i·h2(k)) mod m Minimal (best) Two functions; best spread

8.6 Hashing with Chaining

Separate Chaining resolves collisions by making each slot of the hash table the head of a linked list. All keys that hash to the same index are simply appended to that slot's list, so the table never "overflows."

Trace — table size 10, h(k) = k mod 10, insert {23, 43, 13, 33, 27, 37}

Key h(k) Chain action
23 3 index 3: 23
43 3 index 3: 23 → 43
13 3 index 3: 23 → 43 → 13
33 3 index 3: 23 → 43 → 13 → 33
27 7 index 7: 27
37 7 index 7: 27 → 37

Resulting structure:

Index 0:  (empty)
Index 1:  (empty)
Index 2:  (empty)
Index 3:  23 → 43 → 13 → 33 → null
Index 4:  (empty)
Index 5:  (empty)
Index 6:  (empty)
Index 7:  27 → 37 → null
...

Advantages: the table never fills up; deletion is simple (remove a node from the list); performs well even with a high load factor. Disadvantage: extra memory for pointers; if the hash function is poor, one chain can grow long, degrading search to O(n).

Java Code

import java.util.*;

public class HashChaining {
    LinkedList<Integer>[] table; int size;

    @SuppressWarnings("unchecked")
    HashChaining(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) table[i] = new LinkedList<>();
    }

    void insert(int key)   { table[key % size].add(key); }
    boolean search(int key){ return table[key % size].contains(key); }
    void delete(int key)   { table[key % size].remove((Integer) key); }

    public static void main(String[] args) {
        HashChaining h = new HashChaining(10);
        for (int k : new int[]{23, 43, 13, 33, 27, 37}) h.insert(k);
        System.out.println("Chain at index 3: " + h.table[3]); // [23, 43, 13, 33]
        System.out.println("Chain at index 7: " + h.table[7]); // [27, 37]
        System.out.println("Search 13: " + h.search(13));      // true
    }
}

8.7 Rehashing

Rehashing is the process of increasing the size of the hash table (usually doubling it, kept prime if possible) and re-inserting all existing keys using a hash function adjusted to the new table size. It is performed when the table becomes too full and collisions start hurting performance.

Load Factor

Load factor (λ) = (number of elements stored) / (table size). As λ increases, collisions become more frequent and operations slow down. When λ crosses a threshold (commonly 0.7–0.75), rehashing is triggered to restore efficiency.

Steps of Rehashing

  1. Create a new, larger table (e.g., newSize ≈ 2 × oldSize, ideally a prime).
  2. For every key in the old table, recompute its index with the new table size.
  3. Insert each key into the new table (resolving collisions as usual).
  4. Discard the old table and use the new one.

Example

Old table size m = 5, h(k) = k mod 5, keys inserted: {12, 22, 9, 15}. After 4 elements, λ = 4/5 = 0.8 > 0.7 → rehash.

  • Choose new size m = 11, h(k) = k mod 11:
    • 12 → 1, 22 → 0, 9 → 9, 15 → 4.

New table (well distributed):

Index:  0    1    2   3   4    5   6   7   8   9   10
Value:  22   12   -   -   15   -   -   -   -   9   -

Rehashing spreads the keys out again, lowering the load factor and keeping average operations near O(1). (Java's HashMap rehashes automatically when it exceeds its load factor.)

8.8 Efficiency Comparison of Search Techniques

Technique Best Average Worst Data requirement Structure
Linear Search O(1) O(n) O(n) None (works unsorted) Array/List
Binary Search O(1) O(log n) O(log n) Sorted data Array
Tree Search (BST) O(1) O(log n) O(n) BST (ordered) Tree
Hashing (good hash) O(1) O(1) O(n) Hash table Array + hash

When to use which:

  • Linear Search — small or unsorted data, or when data changes constantly.
  • Binary Search — large sorted arrays searched many times.
  • Tree Search (BST) — dynamic data needing search + insert + delete together, and ordered traversal.
  • Hashing — fastest key-based lookup where ordering is not required (dictionaries, caches, symbol tables).

Important Questions with Full Answers

Short Questions (2 marks each)

Q1. What is searching? Name its two broad categories. Searching is the process of finding the position of a target element (search key) in a collection of data, or reporting that it is absent. Its two broad categories are comparison-based searching (Linear, Binary, Tree search) and hash-based searching (Hashing, which computes the address directly).

Q2. Why does Binary Search require the data to be sorted? Binary Search decides which half of the array to discard by comparing the key with the middle element. This decision (go left if smaller, right if larger) is only valid when the elements are in sorted order; otherwise the discarded half might actually contain the key, making the result incorrect.

Q3. Define collision in hashing. A collision occurs when two different keys are mapped by the hash function to the same index in the hash table, so both would need to occupy the same slot.

Q4. List any three characteristics of a good hash function. A good hash function should be fast to compute (O(1)), distribute keys uniformly across the table to minimize collisions, and be deterministic (the same key always gives the same index). Using the entire key is another desirable property.

Q5. Differentiate between open addressing and separate chaining (one line each). In open addressing, all keys are stored inside the table and, on collision, the algorithm probes for another empty slot within the table. In separate chaining, each slot holds a linked list, and colliding keys are appended to that list.

Q6. Define load factor and rehashing. Load factor λ is the ratio of the number of stored elements to the table size (λ = n/m). Rehashing is the process of creating a larger table and re-inserting all existing keys with a new hash function when λ becomes too high, to keep operations efficient.

Q7. What is primary clustering in linear probing? Primary clustering is the formation of long, continuous blocks of occupied slots in linear probing. As these clusters grow, the number of probes needed for subsequent insertions and searches increases, reducing efficiency.

Q8. State the best-case and worst-case time complexity of Linear Search. Best case is O(1) (the key is the first element); worst case is O(n) (the key is the last element or not present, requiring the whole list to be scanned).

Long Questions (6 marks each)

Q1. Explain Binary Search with its algorithm, a complete trace, and complexity. Compare it with Linear Search.

Binary Search is an efficient technique for sorted arrays that uses divide-and-conquer. It compares the key with the middle element; if equal, the search succeeds; if the key is smaller, it searches the left half; if larger, it searches the right half. Each step halves the search space.

Algorithm: set low = 0, high = n−1; while low ≤ high, compute mid = (low+high)/2; if A[mid] == key return mid; if A[mid] < key set low = mid+1; else set high = mid−1; if the loop ends, return −1.

Trace on [11, 22, 33, 44, 55, 66, 77], key = 55: low=0,high=6,mid=3 → 44<55 → low=4; low=4,high=6,mid=5 → 66>55 → high=4; low=4,high=4,mid=4 → 55==55 → found at index 4 (3 comparisons).

Complexity: best case O(1) (key at middle), average and worst case O(log n).

Comparison: Binary Search runs in O(log n) but requires sorted data and random access; Linear Search runs in O(n) but works on unsorted data and needs no preprocessing. For large, static, sorted datasets that are searched repeatedly, Binary Search is far superior; for small or frequently changing data, Linear Search is simpler.

Q2. What is hashing? Explain the characteristics of a good hash function and describe the types of hash functions with examples.

Hashing is a technique that maps a key directly to an index in a hash table using a hash function, allowing average O(1) storage and retrieval without comparing elements one by one.

Characteristics of a good hash function: it should be fast to compute (O(1)); distribute keys uniformly to minimize collisions; be deterministic (same key → same index); use the entire key; and perform well as the table fills.

Types with examples:

  • Division method: h(k) = k mod m. Example: h(1234) with m=97 = 70.
  • Mid-square method: square the key and take middle digits. Example: 1234² = 1522756 → middle digits 227.
  • Folding method: split the key into parts and add them. Example: 123456 → 12+34+56 = 102 → 102 mod 100 = 2.
  • Multiplication method: h(k) = floor(m·(k·A mod 1)), A≈0.618. Example: k=123, m=100 → 123×0.618=76.014 → 100×0.014 = 1.4 → 1.

Q3. Explain separate chaining with an example and trace. State its advantages and disadvantages compared with open addressing.

Separate chaining resolves collisions by making each hash-table slot the head of a linked list; all keys hashing to the same index are appended to that list.

Trace (m=10, h(k)=k mod 10, keys {23,43,13,33,27,37}): 23, 43, 13, 33 all hash to 3, forming the chain 23→43→13→33 at index 3; 27 and 37 hash to 7, forming 27→37 at index 7.

Advantages: the table never overflows (it can hold more keys than slots); deletion is easy (just remove a node); it degrades gracefully under a high load factor. Disadvantages: it needs extra memory for pointers, and a poor hash function can produce one very long chain, degrading search to O(n). In contrast, open addressing stores everything in the array (better cache locality, no pointer overhead) but can fill up and suffers from clustering.

Q4. Explain Tree Search on a Binary Search Tree with an example, and analyze its best and worst cases.

Tree Search navigates a Binary Search Tree, where every node's left subtree holds smaller keys and its right subtree holds larger keys. Starting at the root, the key is compared with the current node: if equal, found; if smaller, move left; if larger, move right; if a null link is reached, the key is absent.

Example (BST from [50,30,70,20,40,60,80], search 40): 40<50 → go left to 30; 40>30 → go right to 40; 40==40 → found in 3 comparisons.

Best case: the key is at the root → O(1). Average case: in a balanced tree, height ≈ log n → O(log n). Worst case: if the tree is skewed (e.g., keys inserted in sorted order form a chain), height = n → O(n). Self-balancing trees such as AVL or Red-Black guarantee O(log n) even in the worst case.

Long Questions (10 marks each)

Q1. Explain the collision resolution techniques of open addressing — linear probing, quadratic probing, and double hashing — with the probe formula, a worked example/trace, and the clustering behavior of each.

A collision occurs when two keys hash to the same index. In open addressing all keys are stored inside the table, and on collision we probe for another empty slot. Using table size m=10, h(k)=k mod 10, and inserting {23, 43, 13, 33} (all hash to 3):

Linear probing uses index = (h(k)+i) mod m. Trace: 23→slot 3; 43→3 occupied→slot 4; 13→3,4 occupied→slot 5; 33→3,4,5 occupied→slot 6. It is simple and cache-friendly but causes primary clustering — long runs of filled slots that lengthen later probes.

Quadratic probing uses index = (h(k)+i²) mod m. Trace: 23→3; 43→(3+1)=4; 13→(3+4)=7; 33→(3+9)=12 mod 10=2. It reduces primary clustering by spreading probes out, but suffers secondary clustering — keys with the same initial index still follow the same probe sequence.

Double hashing uses index = (h1(k)+i·h2(k)) mod m with a second hash function, e.g., h2(k)=7−(k mod 7). Trace: 23→3; 43→h2=6→(3+6)=9; 13→h2=1→(3+1)=4; 33→h2=2→(3+2)=5. Because the step size differs per key, it eliminates both primary and secondary clustering and gives the best distribution of the three.

Summary: linear probing → primary clustering; quadratic probing → secondary clustering; double hashing → minimal clustering (best), at the cost of computing a second hash function.

Q2. Compare all the search techniques (Linear, Binary, Tree Search, and Hashing) in terms of time complexity, data requirements, and suitable applications. Also explain rehashing and why it is needed.

Technique Best Average Worst Requirement Best used when
Linear Search O(1) O(n) O(n) None Small/unsorted or changing data
Binary Search O(1) O(log n) O(log n) Sorted array Large sorted data searched often
Tree Search O(1) O(log n) O(n) BST Dynamic data (search+insert+delete)
Hashing O(1) O(1) O(n) Hash table Fast key lookup, order not needed

Linear Search is the most general but slowest for large data. Binary Search is very fast but needs sorted data and random access, so it is inefficient for data that changes often (which would require re-sorting). Tree Search combines fast average-case search with dynamic insertion and deletion, and gives sorted order via in-order traversal, but degrades to O(n) if the tree is unbalanced. Hashing offers the fastest average lookup (O(1)) but does not maintain order and degrades to O(n) if collisions are severe.

Rehashing is enlarging the hash table (usually doubling it, kept prime) and re-inserting all keys with a new hash function when the load factor λ = n/m exceeds a threshold (about 0.7). It is needed because, as the table fills, collisions rise sharply and operations slow toward O(n); rehashing spreads the keys across a larger table, lowering λ and restoring average O(1) performance. For example, a size-5 table holding 4 elements (λ = 0.8) is rehashed into a size-11 table, distributing the keys and reducing collisions.

Lab Question

  1. Implement a program to perform Sequential Search, Binary Search, Binary Search Tree (BST) Search, and Hash Table Search using Linear Probing, Quadratic Probing, Double Hashing, and Chaining. Compare the performance of each searching technique by analyzing the number of comparisons and execution time for searching different keys.

End of Unit VIII — Searching.