The simplest form of a search is the S

**equential 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 !

ReplyDeleteHelpful Thanks ^_^

ReplyDelete