Tuesday, December 6, 2011

How to implement Sequential Search in C/C++?

The simplest form of a search is the Sequential Search. This search is applicable to a table organized either as an array or as a linked list. Let us assume that k is an array of n keys, k(0) through k(n-1), and r, an array of records, r(0) through r(n-1), such that k(i) is the key of r(i). Let us also assume that key is a search argument. We wish to return the smallest integer i such that k(i) equals key if such i exists and –1 otherwise.
for(i = 0; i < n; i++)
     return (i);
     return (-1);
We can improve this algorithm by inserting an extra key at the end of an array called ‘sentinel’. Which prevents beyond the upper bound of array error and generating that key will be found preventing from infinite looping.

Source Code

The code is also avalable on GitHub.

#include <iostream> 

using namespace std;
int main()
    int arr[10];
    int no_of_elements, key;
    bool found = false;
    cout << "Enter the number of element: ";
    cin >> no_of_elements;
    for (int i = 0; i < no_of_elements; i++) {
        cout << "arr[" << i << "]: ";
        cin >> arr[i];
    cout << "Enter the value to search: ";
    cin >> key;
    for (int i = 0; i < no_of_elements; i++) {
        if (key == arr[i]) {
            found = true;
            cout << "The value is found at index arr[" << i << "]";
    if (!found) {
        cout << "Key not found!";
    return 0;


Enter the number of element: 7
arr[0]: 8
arr[1]: 9
arr[2]: 45
arr[3]: 12
arr[4]: 36
arr[5]: 75
arr[6]: 16
Enter the value to search: 36
The value is found at index arr[4]

Efficiency of Sequential Search
Best Case: requires only one comparison, so O(1). Worst Case: requires n comparisons, so O(n). Average Case: requires (n+1)/2 comparisons again O(n).