Linear search

 

The sequential search, also known as the linear search, are the most basic search algorithms. Every element in the data set is examined in the order presented until the value being searched for is found. If the value being searched for doesn't exist, a flag value is returned (such as -1 ).

 

As a real world example, pickup the nearest phonebook and open it to the first page of names. We're looking to find the first "Sami". Look at the first name. Is it "Sami"? Probably not (it's probably a name that begins with 'A'). Now look at the next name. Is it "Sami"? Probably not. Keep looking at the next name until you find "Sami".

 

The above is an example of a sequential search. You started at the beginning of a sequence and went through each item one by one, in the order they existed in the list, until you found the item you were looking for. Of course, this probably isn't how you normally look up a name in the phonebook; we'll cover a method similar to the way you probably look up phone numbers later in this guide.

 

Now we'll look at this as related to computer science. Instead of a phonebook, we have an array. Although the array can hold data elements of any type, for the simplicity of an example we'll just use an array of integers, like the following:

 

 

The array we're searching

Lets search for the number 3. We start at the beginning and check the first element in the array. Is it 3?

 

No, not it. Is it the next element?

 

Not there either. The next element?

 

Not there either. Next?

 

 Yes!

We found it!!! Now you understand the idea of linear searching; we go through each element, in order, until we find the correct value.

 

Program

 

The function will take three arguments: the array to search, the number of elements in the array, and a value to search for. The function will return the index into the array that the value was found at, or -1 if the value wasn't found .

 

#include <stdio.h>
#define SIZE 100

int linearSearch( const int [], int, int );

int main()
{
int a[ SIZE ], x, searchKey, element;

for ( x = 0; x <= SIZE - 1; x++ ) /* create data */
a[ x ] = 2 * x;

printf( "Enter integer search key:\n" );
scanf( "%d", &searchKey );
element = linearSearch( a, searchKey, SIZE );

if ( element != -1 )
printf( "Found value in element %d\n", element );
else
printf( "Value not found\n" );

return 0;
}

int linearSearch( const int array[], int key, int size )
{
int n;

for ( n = 0; n <= size - 1; ++n )
if ( array[ n ] == key )
return n;

return -1;
}