Linear Search

This method traverses a list sequentially to locate the search key.

The algorithm that one chooses generally depends on the organization of the array elements. If the elements are in random order, then one should choose the linear search technique.

Algorithm

linearsearch (a,n,item,loc)

Here "a" is an array of the size n. This algorithm finds the location of the element "item" in the array "a". If search item is found, it sets loc to the index of the element; otherwise, it sets loc to -1

Begin for i=0 to (n-1) by 1 do if (a[i] = item) then set loc=I exit endif endfor set loc -1 end

C/C++ Implementation of the Algorithm

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

int linearsearch (int a[], int n, int key)

{

 int i;

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

 {

 if(a[i]==key)

 return i;

 }

 return -1;

}

Analysis of Linear Search

In the best possible case, the item may be found at the first position. In that case, the search operation terminates in success with just one comparison.

The worst case occurs when the item is present at the last position or it is missing from the array. In the former case, the search terminates in success with n comparisons. In the latter case, the search terminates in failure with n comparisons. Thus, we find that in the worst case, linear search carries out n operations.

Complete Program

/**

 * Program that illustrates the working of Linear Search

 * http://www.tech-faq.com

 */

#include <stdio.h>

/**

 * Parameters:

 * a: array to search in

 * n: number of elements in the array

 * key: search key

 *

 * Return Value: index of the first occurence

 * of key in a[], or -1 if not found

 */

int linearsearch (int a[], int n, int key)

{

 int i;

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

 {

 if(a[i]==key)

 return i;

 }

 return -1;

}

int main()

{

 int array[50], num, index, element, key;

 /*Fill the array*/

 puts("How many elements do you want to create the array with? (Max 50)");

 scanf("%d", &num);

 printf("Enter the elements: ");

 fflush(stdout);

 for (index=0; index<num; index++) 

 scanf("%d", &array[index]);

 printf("Enter the search key: ");

 fflush(stdout);

 scanf("%d", &key);

 if ( (index=linearsearch(array, num, key)) != -1)

 printf("The element was found at index: %dn", index);

 else

 printf("Could not find %dn", key);

 return 0;

}