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 an i exists and –1 otherwise.

Algorithm

for(i = 0; i < n; i++)

if(key==k(i))

return (i);

else

return (-1);

We can improve this algorithm by inserting an extra key at the end of 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:

#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;
}

Output

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).