Searching Algorithms in Data Structures with C++ Programs: Linear Search, Binary Search, Hashing, Hash Tables & Collision Resolution

 

Computer Science · Data Structures

Searching Algorithms
in Data Structures

A comprehensive guide covering Linear Search, Binary Search, Hashing, Hash Tables, Collision handling, and Resolution Methods — with step-by-step algorithms, C++ programs, sample outputs, and complexity analysis.

Introduction to Searching Algorithms

What searching means and why it matters in computer science

Searching algorithms are one of the most fundamental concepts in computer science and data structures. Whenever we want to locate a particular piece of information from a large collection of data, we use a searching algorithm. In simple words, searching means finding the location of a specific element in a list, array, or database. For example, imagine you have a phone contact list containing thousands of names. If you want to find a specific contact quickly, your phone uses a search algorithm in the background to locate that name.

Computers handle massive amounts of data every day, and without efficient searching methods, retrieving information would become extremely slow and inefficient. Searching algorithms help reduce the time needed to locate data and improve overall system performance. Some searching methods are very simple and suitable for small datasets, while others are more advanced and designed for large databases and applications.

There are several types of searching techniques used in programming and data structures. Among them, Linear Search, Binary Search, and Hashing-based search methods are the most commonly studied. Understanding searching algorithms is important not only for academic exams but also for practical software development. Many real-world systems like search engines, databases, and recommendation systems depend on efficient searching techniques to deliver results instantly.

⚡

System Efficiency

Efficient search algorithms reduce the number of steps to find data, saving time and computational resources across all applications.

🏦

System Performance

Banking, e-commerce, and online services rely on optimized search methods to process queries quickly and maintain great user experience.

🗂️

Data Organization

Search algorithms help developers choose the right data structure — sorted arrays for Binary Search, hash tables for O(1) retrieval.

🌐

Everywhere in Tech

Search engines, databases, social media, file systems, and recommendation engines all depend on efficient searching techniques.

Real-Life Examples of Searching Algorithms

Searching algorithms may sound like a purely technical concept, but they are used everywhere in daily life through technology. Whenever we use digital services, we indirectly interact with searching algorithms.

Everyday Analogies

Linear Search Searching a name in an unsorted notebook — checking every name one by one from the beginning.

Binary Search Searching a word in a dictionary — open the middle, then decide to go left or right.

Hashing Google or Amazon search — keywords mapped to data locations via hash tables for near-instant results.

These real-life scenarios show that searching algorithms are not just theoretical concepts taught in classrooms. They are essential tools that power the digital systems we use every day.

Searching Algorithms — In Depth

Working principles, algorithms, C++ programs, and outputs

1

Linear Search

O(n) Time Complexity

Linear Search is the simplest searching algorithm. It checks each element of the list one by one until the desired element is found or the entire list has been examined. It is often the first searching algorithm that students learn.

The algorithm starts from the first element and compares it with the target value. If they match, the position is returned. If not, it moves to the next element and repeats. The biggest advantage is that it works on unsorted data. However, it becomes slow for large datasets since every element may need to be checked.

BestO(1) AvgO(n) WorstO(n) SpaceO(1)

Algorithm Steps

1. Start from the first element of the array.
2. Compare the current element with the target value.
3. If they match, return the position of the element.
4. If they do not match, move to the next element.
5. Repeat the process until the element is found or the array ends.
6. If the element is not found, return "Not Found".

Trace Example — Array: 10, 20, 30, 40, 50 | Search: 30

Step 1 Compare 10 with 30 → No match → move next

Step 2 Compare 20 with 30 → No match → move next

Step 3 Compare 30 with 30 → Match! Position 3 ✓

C++ · linear_search.cpp

#include <iostream>
using namespace std;

int main()
{
    int arr[10], n, key, i;

    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter elements:\n";
    for(i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "Enter element to search: ";
    cin >> key;

    for(i = 0; i < n; i++) {
        if(arr[i] == key) {
            cout << "Element found at position " << i + 1 << endl;
            return 0;
        }
    }

    cout << "Element not found";
    return 0;
}

Sample Output

Enter number of elements: 5
Enter elements:
10 20 30 40 50
Enter element to search: 30
Element found at position 3

Advantages & Disadvantages

Aspect	Linear Search
Data Requirement	Works on unsorted data ✅
Implementation	Very simple, beginner-friendly ✅
Speed	Slow for large datasets ❌
Time Complexity	O(n)
Extra Memory	No extra memory needed ✅

2

Binary Search

O(log n) Time Complexity

Binary Search is a much faster searching algorithm compared to Linear Search, but it works only under one condition: the data must be sorted. Instead of checking each element one by one, it repeatedly divides the dataset into two halves and determines which half contains the target value.

By eliminating half of the remaining elements at each step, Binary Search significantly reduces the number of comparisons required. This results in a time complexity of O(log n), which is dramatically faster than O(n) for large datasets. For example, with 1,000,000 elements, Binary Search needs at most 20 comparisons.

BestO(1) AvgO(log n) WorstO(log n) SpaceO(1)

Algorithm Steps

1. Start with the middle element of the sorted array.
2. If the middle element equals the search element, return its position.
3. If the search element is smaller than the middle element, search the left half.
4. If it is larger, search the right half.
5. Repeat until the element is found or the search range becomes empty.

Trace Example — Array: 10, 20, 30, 40, 50 | Search: 40

Step 1 low=0, high=4 → mid=2 → arr[2]=30 < 40 → search right half

Step 2 low=3, high=4 → mid=3 → arr[3]=40 == 40 → Found at position 4 ✓

C++ · binary_search.cpp

#include <iostream>
using namespace std;

int main()
{
    int arr[10], n, key;
    int low = 0, high, mid;

    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter sorted elements:\n";
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "Enter element to search: ";
    cin >> key;

    high = n - 1;

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

        if(arr[mid] == key) {
            cout << "Element found at position " << mid + 1;
            return 0;
        }
        else if(arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    cout << "Element not found";
    return 0;
}

Sample Output

Enter number of elements: 5
Enter sorted elements:
10 20 30 40 50
Enter element to search: 40
Element found at position 4

Advantages & Limitations

Aspect	Binary Search
Data Requirement	Requires sorted data ⚠️
Speed	Very fast for large datasets ✅
Time Complexity	O(log n)
Extra Memory	No extra memory needed ✅
Data Structure	Works best with arrays (direct access) ✅

3

Hashing Technique

O(1) Average Time

Hashing is an advanced searching technique used to store and retrieve data quickly. Instead of searching through elements sequentially, hashing uses a mathematical function called a hash function to calculate the location where the data should be stored. This allows the system to access data directly without scanning the entire dataset.

In hashing, data is stored in a special structure known as a hash table. Each element has a unique key that is passed through a hash function. The hash function converts the key into a numeric value called the hash value, which determines the index where data should be stored. On average, operations like insertion, deletion, and searching can be performed in constant time O(1).

BestO(1) AvgO(1) WorstO(n) SpaceO(n)

How Hash Functions Work

A hash function takes an input value (called a key) and converts it into a fixed-size integer known as the hash value. This value determines the position where the data will be stored in the hash table.

Hash Function Formula

Hash(key) = key mod table_size

Example: key = 27, table_size = 10 → 27 mod 10 = 7 → stored at index 7

Algorithm Steps (Hashing)

1. Take the key value.
2. Apply the hash function: index = key % table_size.
3. Calculate the index in the hash table.
4. Store the element at that index.

Characteristics of a Good Hash Function

✓ Distributes data evenly across the entire table

✓ Fast to compute — minimal processing overhead

✓ Minimizes collisions to the greatest extent possible

4

Hash Table

O(1) Average Search / Insert / Delete

A Hash Table is a data structure used to store key-value pairs. It uses a hash function to compute an index where the value should be stored. This allows the system to quickly locate data using its key — without scanning the entire dataset.

The structure typically includes an array of slots or buckets. Each slot stores data associated with a specific key. When a key is passed through the hash function, the resulting hash value determines the index where data will be stored. Because of their speed, hash tables are used in Python dictionaries, Java HashMaps, and JavaScript associative arrays.

Hash Table Example

Hash Function = key % 10

key = 25 → 25 % 10 = 5 → stored at index 5

C++ · hash_table.cpp

#include <iostream>
using namespace std;

int main()
{
    int hashTable[10];

    for(int i=0; i<10; i++)
        hashTable[i] = -1;

    int key;

    cout << "Enter 5 values:\n";

    for(int i=0; i<5; i++){
        cin >> key;
        int index = key % 10;
        hashTable[index] = key;
    }

    cout << "\nHash Table:\n";

    for(int i=0; i<10; i++){
        cout << "Index " << i << " : " << hashTable[i] << endl;
    }

    return 0;
}

Sample Output

Enter 5 values:
15  23  10  44  52

Hash Table:
Index 0 : 10
Index 1 : -1
Index 2 : 52
Index 3 : 23
Index 4 : 44
Index 5 : 15
Index 6 : -1
Index 7 : -1
Index 8 : -1
Index 9 : -1

5

Collision in Hashing

When two keys share the same index

A collision occurs when two different keys generate the same hash value. In other words, both keys try to occupy the same index in the hash table. This situation creates a conflict because a single slot cannot store multiple values directly.

Collisions are common in hashing because the number of possible keys is usually larger than the number of slots in the hash table. Even with a good hash function, it is impossible to completely eliminate collisions. When a collision occurs, the system must decide how to store both values without losing data — this is where collision resolution techniques come into play.

Collision Example — Table Size = 10

Key 25 → 25 % 10 = Index 5

Key 35 → 35 % 10 = Index 5 ⚠ COLLISION

Key 45 → 45 % 10 = Index 5 ⚠ COLLISION

Both keys 25, 35, and 45 map to index 5 → Collision! Must use a resolution method.

Why Collisions Occur

Collisions occur mainly due to the limited size of the hash table. When many keys are inserted into a small table, the probability of two keys mapping to the same index increases.

Another reason is the design of the hash function. If it does not distribute values evenly, certain slots become overcrowded while others remain empty. To manage these situations, programmers use Chaining or Open Addressing.

6

Collision Resolution: Chaining

Separate Chaining with Linked Lists

The Chaining method (also called Separate Chaining) is one of the most common ways to handle collisions in hash tables. In this method, each slot of the hash table contains a linked list. When multiple keys produce the same hash value, they are stored in the linked list associated with that slot.

This approach ensures that multiple elements can coexist even when they share the same hash value. Chaining is relatively easy to implement and works well when the number of collisions is moderate. The hash table never becomes completely full because new elements can always be added to the linked list.

Visual — Index 5 stores multiple colliding keys

Index 5 25 → 35 → 45 → NULL

Index 0 20 → NULL

Others Empty (NULL)

Algorithm Steps (Chaining)

1. Compute hash index using hash function: index = key % size.
2. If the slot is empty, insert the element directly.
3. If a collision occurs, insert the element into the linked list at that index.

C++ · chaining.cpp

#include <iostream>
#include <list>
using namespace std;

int main()
{
    int size = 10;
    list<int> table[10];

    int n, key;

    cout << "Enter number of elements: ";
    cin >> n;

    for(int i=0; i<n; i++){
        cout << "Enter value: ";
        cin >> key;
        int index = key % size;
        table[index].push_back(key);
    }

    cout << "\nHash Table using Chaining:\n";

    for(int i=0; i<size; i++){
        cout << i << " : ";
        for(auto x : table[i])
            cout << x << " -> ";
        cout << endl;
    }

    return 0;
}

Sample Output

Enter number of elements: 4
Enter value: 25
Enter value: 35
Enter value: 15
Enter value: 20

Hash Table using Chaining:
0 :
1 :
2 :
3 :
4 :
5 : 25 -> 35 -> 15 ->
6 :
7 :
8 :
9 : 20 ->

Advantages & Disadvantages of Chaining

Aspect	Chaining
Table Full?	Never becomes full — always extendable ✅
Hash Function Sensitivity	Less sensitive to quality of hash function ✅
Extra Memory	Requires pointer storage for linked lists ❌
Cache Performance	May reduce cache efficiency vs arrays ❌

7

Collision Resolution: Open Addressing

Linear Probing · Quadratic Probing · Double Hashing

Open Addressing is another method used to resolve collisions. Unlike chaining, this method stores all elements directly inside the hash table. When a collision occurs, the algorithm searches for another empty slot in the table according to a specific pattern called a probe sequence.

In open addressing, the algorithm checks alternative positions until it finds an empty slot. During searching, it follows the same sequence to locate the element. This technique stores data in contiguous memory locations, which improves cache efficiency.

Linear Probing Example — Index 5 occupied

Try Index 5 Occupied by 25 → collision!

Try Index 6 Empty → Insert 35 at index 6 ✓

Try Index 7 Empty → Insert 15 at index 7 ✓

Types of Probing Techniques

Linear Probing

Checks the next slot sequentially until an empty slot is found. Simple and cache-friendly, but can suffer from clustering.

Quadratic Probing

Uses a quadratic function to calculate the next slot. Reduces clustering compared to linear probing but slightly more complex.

Double Hashing

Uses a second hash function to determine step size. Provides the best distribution but requires more computation.

Algorithm Steps (Open Addressing)

1. Calculate hash index: index = key % table_size.
2. If slot is empty → insert element.
3. If slot is occupied (collision) → move to next slot: index = (index + 1) % table_size.
4. Repeat until an empty slot is found.

C++ · open_addressing.cpp

#include <iostream>
using namespace std;

int main()
{
    int table[10];

    for(int i=0; i<10; i++)
        table[i] = -1;

    int key;

    cout << "Enter 5 values:\n";

    for(int i=0; i<5; i++){
        cin >> key;

        int index = key % 10;

        while(table[index] != -1){
            index = (index + 1) % 10; // linear probing
        }

        table[index] = key;
    }

    cout << "\nHash Table using Open Addressing:\n";

    for(int i=0; i<10; i++){
        cout << "Index " << i << " : " << table[i] << endl;
    }

    return 0;
}

Sample Output

Enter 5 values:
25  35  15  20  45

Hash Table using Open Addressing:
Index 0 : 20
Index 1 : -1
Index 2 : -1
Index 3 : -1
Index 4 : -1
Index 5 : 25
Index 6 : 35
Index 7 : 15
Index 8 : 45
Index 9 : -1

Quick Comparison of Searching Methods

Data requirements, speed, and time complexity at a glance

Method	Data Requirement	Speed	Time Complexity
Linear Search	Unsorted — no restriction	Slow for large data	O(n)
Binary Search	Must be sorted first	Fast	O(log n)
Hashing	Uses hash function	Very Fast	O(1) average

Conclusion

Searching algorithms are essential tools in computer science that allow systems to locate data efficiently. From simple methods like Linear Search to advanced techniques like Hashing, each algorithm plays an important role depending on the structure and size of the data.

Linear Search is easy to understand and works well with small or unsorted datasets, while Binary Search significantly improves performance by repeatedly dividing sorted data into halves. Hashing takes searching efficiency to another level by mapping keys directly to memory locations through hash functions, enabling O(1) average-time operations.

However, hashing introduces the challenge of collisions, which must be handled using techniques like Chaining and Open Addressing. Understanding these algorithms helps students build a strong foundation in data structures and prepares them for more advanced topics in computer science.

Frequently Asked Questions

Common questions about searching algorithms

1 What is a searching algorithm?

A searching algorithm is a method used to find a specific element within a dataset such as an array, list, or database. It determines whether the element exists and identifies its position.

2 What is the difference between Linear Search and Binary Search?

Linear Search checks elements one by one and works on unsorted data with O(n) complexity. Binary Search repeatedly divides a sorted dataset into halves to locate the target element much faster with O(log n) complexity — but requires the data to be sorted first.

3 What is hashing in data structures?

Hashing is a technique that uses a hash function to map keys to specific positions in a hash table, allowing extremely fast data retrieval. On average, search, insertion, and deletion operations take O(1) constant time.

4 What is a collision in hashing?

A collision occurs when two different keys produce the same hash value and attempt to store data in the same index of the hash table. Collisions are common and are handled using collision resolution techniques.

5 What are the main collision resolution methods?

The two main methods are Chaining — which uses linked lists to store multiple elements in one slot — and Open Addressing — which finds another empty slot in the table using probing techniques such as Linear Probing, Quadratic Probing, and Double Hashing.