Sequential Search

Sequential Search, also known as Linear Search, is the most fundamental and straightforward searching algorithm.

Imagine you have a shuffled deck of cards and you are looking for the "Queen of Hearts." You start from the top of the deck and check every single card one by one until you find it or reach the bottom. That is exactly how Linear Search works.

It checks every element in the array sequentially from the first index (0) to the last index (n-1) until the target key is found or the list ends.

How Linear Search Works?

• Start from the first element of the array.
• Compare the target element with the current element.
• If a match is found, return the index.
• If not, move to the next element.
• Repeat until the end of the list.
• If the target is not found, return -1 or indicate "not found."

Example of Linear Search

Let’s assume we have an array: arr = [15, 7, 23, 8, 42, 16, 4] and we want to search for Key = 16.

We will trace the algorithm step by step:

• Step 1: Start at index 0. Compare arr[0] (which is 15) with 16. Not a match.
• Step 2: Move to index 1. Compare arr[1] (which is 7) with 16. Not a match.
• Step 3: Move to index 2. Compare arr[2] (which is 23) with 16. Not a match.
• Step 4: Move to index 3. Compare arr[3] (which is 8) with 16. Not a match.
• Step 5: Move to index 4. Compare arr[4] (which is 42) with 16. Not a match.
• Step 6: Move to index 5. Compare arr[5] (which is 16) with 16. Match Found!
• Result: The algorithm stops and returns the index 5.

What if the key is not in the array?

If we searched for Key = 100, the algorithm would traverse the entire array. After checking arr[6] = 4 (the last element), it would exit the loop and return -1, indicating the key was not found.

Algorithm for Sequential Search

Here is the step-by-step pseudocode, designed for absolute clarity:

Algorithm: LinearSearch(arr, n, key)
Input:  arr[] - The array to search in
        n - Total number of elements in the array
        key - The element to find
Output: Index of the key if found, otherwise -1

Step 1: START
Step 2: Set i = 0
Step 3: Repeat Step 4 and Step 5 while i < n
Step 4:     IF arr[i] == key THEN
Step 5:         RETURN i   [Successful Search]
Step 6:     i = i + 1
Step 7: RETURN -1          [Unsuccessful Search]
Step 8: END

Implementation in C Programming

Below is the complete C program to implement Linear Search. It includes both the search function and the main driver code.

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int n, int key) {
    // Loop through each element in the array
    for (int i = 0; i < n; i++) {
        // If current element matches the key, return its index
        if (arr[i] == key) {
            return i;
        }
    }
    // If the loop finishes, the key was not found
    return -1;
}

int main() {
    // Initialize the array
    int arr[] = {15, 7, 23, 8, 42, 16, 4};
    // Calculate the size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
    // Define the key to search for
    int key = 16;
    
    // Call the search function
    int result = linearSearch(arr, n, key);
    
    // Display the result
    if (result != -1) {
        printf("Element %d found at index %d.\n", key, result);
    } else {
        printf("Element %d not found in the array.\n", key);
    }
    return 0;
}

Output:

Element 16 found at index 5.

Time and Space Complexity Analysis

Understanding the efficiency is crucial. Let n be the number of elements.

Time Complexity

The number of comparisons determines the time.

Why is the worst case O(n)?

If the key is absent, the algorithm must check every single element before concluding it isn't there. As n grows, the time taken grows linearly, hence O(n).

Space Complexity

Linear search does not use any extra data structures (like temporary arrays or recursion stacks). It only uses a few loop variables.

• Space Complexity: O(1) (Constant space).

Advantages of Sequential Search

1. Extremely Simple: It is the easiest algorithm to implement and debug.
2. No Preprocessing Required: The data does not need to be sorted. It works on any unsorted list.
3. Versatile: Works well on different data structures, including arrays and linked lists (unlike Binary Search which needs random access).
4. Handles Small Datasets: For tiny arrays (e.g., < 20 elements), its simplicity makes it faster than complex algorithms due to lower overhead.

Disadvantages of Sequential Search

1. Inefficient for Large Data: As the data grows, the time increases linearly. It is too slow for large-scale applications.
2. High Worst-Case Cost: In the worst case, it scans the entire dataset, wasting CPU cycles.
3. Not Suitable for Real-Time Systems: If you need a response in milliseconds for millions of records, Linear Search will fail.

When to Use Sequential Search?

• When the dataset is small.
• When the array is unsorted and you only need to perform a search once or twice.
• When you are dealing with a data structure that does not support random access (like a linked list).
• When you prioritize simplicity over speed.

Practical Real-World Analogy

Imagine you are a receptionist at a small office. You have a physical stack of 20 visitor forms (unsorted) and someone asks for a specific name. You would just flip through the stack quickly this is Linear Search. 

However, if you had 10,000 forms, you would definitely want an organized filing system (like sorting or hashing) to find it faster!