Searching and Hashing

Data Structures and Algorithms

Finding information efficiently in a collection of data.

Total Duration: 4 Hours

Learning Outcomes

Understand searching techniques
Implement Sequential Search
Implement Binary Search
Understand Hashing Concepts
Design Hash Tables
Resolve Hash Collisions

What is Searching?

Searching is the process of locating a specific element in a collection of data.

Example:

[10, 25, 33, 47, 59, 68]

Find: 47

Why Searching is Important?

Google Search
Library Management Systems
Student Databases
Online Shopping
Banking Systems
Operating Systems

Real World Example

Finding a Student Record

Roll No	Name
101	Ram
102	Sita
103	Hari

How quickly can we find Roll No 103?

Types of Searching

1. Sequential (Linear) Search

Check elements one by one.

2. Binary Search

Repeatedly divide the search space into half.

Searching Performance

Method	Best Case	Worst Case
Sequential Search	O(1)	O(n)
Binary Search	O(1)	O(log n)

Faster searching becomes critical when datasets grow large.

Module Roadmap

Sequential Search
Binary Search
Hashing
Hash Functions
Hash Tables
Collision Resolution

8.1.1 Sequential Search

Sequential Search (Linear Search) checks each element one by one until the target is found.

No sorting is required.

How Sequential Search Works

Array = [12, 25, 8, 41, 19, 33]

Target = 19

Start from the first element.

Compare each element with the target.

Stop when found or end of array reached.

Visualization

Compare 12 ✗

Compare 25 ✗

Compare 8 ✗

Compare 41 ✗

Compare 19 ✓ Found

Dry Run Example

Array = [5, 9, 3, 7, 2]

Target = 7

Step	Element	Result
1	5	Not Found
2	9	Not Found
3	3	Not Found
4	7	Found

Algorithm

Step 1: Start

Step 2: Read array and target

Step 3: Compare target
        with each element

Step 4: If match found
        return position

Step 5: Otherwise continue

Step 6: If end reached
        return NOT FOUND

Step 7: Stop

Pseudocode

LINEAR_SEARCH(A, n, key)

for i = 0 to n-1

    if A[i] == key
        return i

return -1

C Program


#include <stdio.h>

int linearSearch(int arr[],
                 int n,
                 int key)
{
    for(int i=0;i<n;i++)
    {
        if(arr[i]==key)
            return i;
    }

    return -1;
}

int main()
{
    int arr[] = {12,25,8,41,19};

    int pos =
      linearSearch(arr,5,19);

    printf("%d",pos);

    return 0;
}

Best Case Analysis

Array = [19, 12, 25, 8, 41]

Target = 19

Found at first position.

Comparisons = 1

Time Complexity = O(1)

Worst Case Analysis

Array = [12,25,8,41,19]

Target = 100

Target does not exist.

Every element must be checked.

Time Complexity = O(n)

Average Case Analysis

On average, the target is found around the middle of the list.

Comparisons ≈ n/2

Complexity = O(n)

Advantages

Very simple
Works on unsorted data
Easy to implement
No extra memory required

Disadvantages

Slow for large datasets
Many comparisons
Not suitable for big databases

Applications

Small datasets
Searching in unsorted lists
Finding records in simple systems
Embedded systems

Classroom Activity

Find 45 using Sequential Search

[10, 15, 22, 45, 60, 72]

How many comparisons are needed?

Answer: 4 Comparisons

Quick Quiz

Does Linear Search require sorting?
What is its worst-case complexity?
When should we use it?

Next Topic

8.1.2 Binary Search

Can we search faster than O(n)?

8.1.2 Binary Search

Binary Search is a fast searching algorithm that repeatedly divides the search space into two halves.

Works only on sorted data.

Why Binary Search?

Elements	Linear Search	Binary Search
1,000	Up to 1,000 checks	≈ 10 checks
1,000,000	Up to 1,000,000 checks	≈ 20 checks

Huge improvement for large datasets.

Important Requirement

Array Must Be Sorted

[2, 5, 8, 11, 15, 20, 25]

Without sorting, Binary Search cannot work correctly.

Divide and Conquer

Find middle element
Compare with target
Discard half of the data
Repeat

Searching 15

[2, 5, 8, 11, 15, 20, 25]

Middle = 11

15 > 11

Ignore left half

Remaining Search Space

[15, 20, 25]

Middle = 20

15 < 20

Ignore right half

Final Search Space

[15]

Found!

Key Variables

low  = first index

high = last index

mid  = (low + high)/2

Search happens between low and high.

Dry Run

Array = [2,5,8,11,15,20,25]
Target = 15

low	high	mid	A[mid]
0	6	3	11
4	6	5	20
4	4	4	15

Binary Search Algorithm

1. Set low = 0

2. Set high = n-1

3. Find mid

4. Compare target with mid

5. If equal → Found

6. If smaller → Search left

7. If larger → Search right

8. Repeat until found

Pseudocode (Iterative)

BinarySearch(A,n,key)

low = 0
high = n-1

while low <= high

    mid = (low+high)/2

    if A[mid] == key
        return mid

    else if key < A[mid]
        high = mid - 1

    else
        low = mid + 1

return -1

C Program (Iterative)


int binarySearch(int arr[],
                 int n,
                 int key)
{
    int low = 0;
    int high = n - 1;

    while(low <= high)
    {
        int mid =
           (low+high)/2;

        if(arr[mid]==key)
            return mid;

        if(key < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -1;
}

Recursive Binary Search

The algorithm naturally divides the problem into smaller subproblems.

Therefore recursion is a natural fit.

Recursive Pseudocode

BinarySearch(A,low,high,key)

if low > high
    return -1

mid=(low+high)/2

if A[mid]==key
    return mid

if key < A[mid]
    search left half

else
    search right half

Recursive C Program


int binarySearch(
int arr[],
int low,
int high,
int key)
{
    if(low > high)
        return -1;

    int mid =
       (low+high)/2;

    if(arr[mid]==key)
        return mid;

    if(key < arr[mid])
        return binarySearch(
          arr,low,
          mid-1,key);

    return binarySearch(
          arr,
          mid+1,
          high,key);
}

Complexity Derivation

n

n/2

n/4

n/8

n/16

Each step removes half of the data.

Mathematical Proof

n / 2^k = 1

n = 2^k

k = log₂(n)

Time Complexity = O(log n)

Complexity Analysis

Case	Complexity
Best	O(1)
Average	O(log n)
Worst	O(log n)

Linear vs Binary Search

Feature	Linear	Binary
Sorted Data	No	Yes
Worst Case	O(n)	O(log n)
Implementation	Easy	Moderate

Exercise

[3,6,9,12,15,18,21,24,27]

Find 24

Determine low, high and mid for each iteration.

Quick Quiz

Can Binary Search work on unsorted data?
What is its worst-case complexity?
Why is it called Divide and Conquer?

Next Topic

8.2 Hashing

Can we search even faster than O(log n)?

Hashing aims for O(1) average search time.

8.2 Hashing

Fast Searching Using Hash Tables

Goal: Achieve O(1) average search time.

Motivation

We improved searching from:

Sequential Search → O(n)
Binary Search → O(log n)

Can we search in almost constant time?

Hashing provides the answer.

Real World Examples

Dictionary word lookup
Database indexing
Password verification
Caching systems
Compiler symbol tables
Routing tables

Dictionary ADT

Dictionary stores:

(Key, Value)

Key	Value
101	Ram
102	Sita

Direct Access Concept

Roll Number = 105

Store directly at Index 105

Search becomes O(1)

But memory usage becomes huge.

Problem with Direct Access

Student ID = 9999999

Need an enormous array.

Memory waste becomes unacceptable.

Solution → Hash Function

Hash Function

A function that converts a key into an array index.

index = h(key)

Example:

h(35)=5
h(27)=7

Simple Hash Function

h(key) = key mod 10

Key	Index
23	3
41	1
57	7
62	2

Hash Table

Index     Data

0         -

1         41

2         62

3         23

4         -

5         -

6         -

7         57

Hashing Process

Receive Key
Apply Hash Function
Generate Index
Store Data
Retrieve Data Later

Characteristics of Good Hash Function

Fast computation
Uniform distribution
Few collisions
Deterministic

Collision

Two keys generate the same index.

h(25)=5
h(35)=5

Both want location 5.

Collision Visualization

Index 5

25
35

What should we do now?

Collision Resolution Techniques

Separate Chaining
Linear Probing
Quadratic Probing
Double Hashing

Separate Chaining

Store multiple elements in a linked list.

Index 5

25 → 35 → 45

Advantages of Chaining

Simple
Easy insertion
Flexible size

Disadvantages of Chaining

Extra memory
Pointer overhead
Cache inefficiency

Linear Probing

Search next empty location.

h(k) = index

index occupied?

Try:
index+1
index+2
index+3
...

Linear Probing Example

Table Size = 10

25 → 5

35 → 5 (collision)

Store at 6

5 : 25

6 : 35

Primary Clustering

Consecutive occupied locations form clusters.

Quadratic Probing

h(k)+1²

h(k)+2²

h(k)+3²

...

Reduces clustering.

Quadratic Probing Example

h(35)=5

Collision

Try:
5+1² = 6

occupied

Try:
5+2² = 9

Store at index 9.

Double Hashing

Index

=
h1(key)
+
i*h2(key)

Uses a second hash function.

Produces better distribution.

Double Hashing Example

h1(k)=k mod 10

h2(k)=7-(k mod 7)

Collision resolution becomes more random.

Load Factor

α = n / m

n = number of stored keys m = table size

Higher load factor means more collisions.

Load Factor Example

Stored Keys = 8

Table Size = 10

α = 8/10 = 0.8

80% full

Complexity Analysis

Operation	Average
Insert	O(1)
Search	O(1)
Delete	O(1)

Worst Case

If many collisions occur:

Search = O(n)

Hash table performance depends heavily on the hash function.

Comparison of Searching Techniques

Method	Complexity
Sequential Search	O(n)
Binary Search	O(log n)
Hashing	O(1)

Applications of Hashing

Databases
Web Caches
Password Storage
Compilers
Blockchain Systems
Distributed Systems

Classroom Activity

Hash Function

h(k)=k mod 10

Insert:

23, 15, 44, 52, 35

Construct the hash table manually.

Quiz

What is a hash function?
What is a collision?
Difference between chaining and probing?
What is load factor?
Why can hashing achieve O(1)?

Module Summary

Sequential Search → O(n)
Binary Search → O(log n)
Hashing → O(1) Average
Hash Tables store Key-Value pairs
Collisions require resolution techniques

Thank You

Questions?

References

Books and Online Resources

Searching Algorithms, Binary Search, Hashing and Hash Tables

Primary Textbooks

Data Structures and Algorithm Analysis in C
Mark Allen Weiss
Pearson Education

Data Structures Using C
Reema Thareja
Oxford University Press

Introduction to Algorithms (CLRS)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
MIT Press

Additional Reference Books

Algorithms
Robert Sedgewick & Kevin Wayne
Addison-Wesley

Data Structures Through C in Depth
S. K. Srivastava & Deepali Srivastava

The Art of Computer Programming, Vol. 3
Donald E. Knuth
Sorting and Searching

Online References

GeeksforGeeks – Searching Algorithms and Hashing
https://www.geeksforgeeks.org

Programiz – Binary Search and Hash Tables Tutorials
https://www.programiz.com

Visualgo – Interactive Search and Hash Table Visualizations
https://visualgo.net

Research & Technical Articles

Knuth, D. E. (1998)
The Art of Computer Programming, Volume 3: Sorting and Searching

Carter, J. L. & Wegman, M. N. (1979)
Universal Classes of Hash Functions

Pagh, R. & Rodler, F. F. (2004)
Cuckoo Hashing

Recommended Learning Resources

Topic	Resource
Sequential Search	CLRS Chapter on Searching
Binary Search	Programiz & Visualgo
Hash Functions	Weiss & GeeksforGeeks
Collision Resolution	CLRS & Knuth

End of Chapter 8

Searching and Hashing

Next Chapter: Sorting Algorithms