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.
Algorithm
for(i = 0; i < n; i++)
if(key==k(i))
return (i);
else
return (-1);
if(key==k(i))
return (i);
else
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;
}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).
thanks , it works fine !
Helpful Thanks ^_^