Linear search algorithm/program in data structures using C

Linear search/ Sequential search

Linear search (also called as sequential search) is a simple search algorithm. It is used to search a key in a list of keys. It compares each key in list starting from the first key to the last until it finds the required key.

Example:

                              Index                                    0      1     2     3     4

20

67

11

90

19

From the list of keys above you have to find the key 90. You are going to return whether 90 exist or not. If exists, you have to return it’s position.

Linear search compares the key 90 with the value stored at index 0, then with the value stored at index 1 and so on until it finds the entry that is matching with the key or to the end of the list.

If the key is found, it returns ‘FOUND’ and the index at which it is found. If not, it returns ‘NOT FOUND’.

Algorithm

Algorithm Linear (a[], total_keys, key_to_find)

{

flag := 0;

for (i =0; i <= total_keys-1; i++)

          if (a[i] == key_to_find)

                   flag := 1;

if (flag == 1)

          print ‘FOUND’;

else

print ‘NOT FOUND’;

}

Algorithm Description:

  

Algorithm	Description
1:  Linear (a[], total_keys, key_to_find) 2:  { 3:  flag := 0; 4:  for (i = 0; i <= total_keys - 1; i++) 5:         if (a[i] == key_to_find) 6:                     flag := 1; 7:  if (flag == 1) 8:         print ‘FOUND’; 9:  else 10:       print ‘NOT FOUND’; 11: }	3: Set the flag with 0 4: Scans entire array from index 0 to n-1 5: Compares each array element with key 6: If found, set the flag with 1 8: After array scan, if flag is 1 return FOUND 10: Else return NOT FOUND

************

Click here for linear search program in C

Click here for Binary Search algorithm 

Linear search algorithm in data structures

Linear search using C

Sequential search algorithm

Sequential search pseudocode

Explain linear search algorithm