Linear Search

With a linear search technique, you look at every element in the array, one-at-a-time beginning at the first. When the value is found, quit immediately. If you get through the entire array without quitting, then the search is unsuccessful -- the value is not in the array.

Linear Search

	
int LinearSearch (int a[], int aSize, int toFind) 
{ 
     // Look through all items, starting at the front. 
     for (int i = 0; i < aSize; i++)     
         if (a[i] == toFind)            
             return i; 
  
     // You've gone through the whole list without success.  
     return -1; 
}
      linearSearch.cpp

Example

We have a list of integer values:	
int list[12] = {3,15,2,8,7,1,14,38,10,-2,61,5};

(1) 
Suppose we wish to search this one-dimensional array for the value 10:
int index = LinearSearch(list,12,10); 

The figure below, shows how linear search works:.
start here ...... ...... ...go through these ...... ...... stop here
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
3 15 2 8 7 1 14 38 10   -2   61   5
0 1 2 3 4 5 6 7 8 9 10 11

After control returns to the activating function, index will contain 8. 
(2)
Suppose we wish to search this one-dimensional array for the value 25:
int index = LinearSearch(list,12,25); 

The figure below, shows how linear search works:.
start here ...... ...... ...... ...... ...go through these ...... ...... ...... ...... stop here
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
3 15 2 8 7 1 14 38 10   -2   61   5
0 1 2 3 4 5 6 7 8 9 10 11

After control returns to the activating function, index will contain -1 meaning that the function did not find 25 in the array. The search goes all the way to the end of the array, since 25 is not in the list.

Summary

Linear search is useful for when your list is full of random data, when your data cannot be organized in a specific order such as ascending/descending order. It's useful when a list isn't sorted. While linear search isn't the most efficient for large datasets, it is still widely used in real life when certain conditions apply.