7.7. Searching Arrays with Linear Search

Often a programmer will be working with large amounts of data stored in arrays. It may be necessary to determine whether an array contains a value that matches a certain key value. The process of finding a particular element of an array is called searching. In this section we discuss the simple linear search.

Linear Search

The linear search (Fig. 7.19 , lines 37–44) compares each element of an array with a search key (line 40). Because the array is not in any particular order, it is just as likely that the value will be found in the first element as the last. On average, therefore, the program must compare the search key with half the elements of the array. To determine that a value is not in the array, the program must compare the search key to every element of the array.

Fig. 7.19. Linear search of an array.

 1   // Fig. 7.19: fig07_19.cpp
 2   // Linear search of an array.
 3   #include <iostream>
 4   using std::cout;
 5   using std::cin;
 6   using std::endl;
 7
 8   int linearSearch( const int [], int, int ); // prototype
 9
10   int main()
11   {
12      const int arraySize = 100; // size of array a
13      int a[ arraySize ]; // create array a
14      int searchKey; // value to locate in array a
15
16      for ( int i = 0; i < arraySize; i++ )
17         a[ i ] = 2 * i; // create some data
18
19      cout << "Enter integer search key: ";
20      cin >> searchKey;
21
22      // attempt to locate searchKey in array a             
23      int element = linearSearch( a, searchKey, arraySize );
24
25      // display results
26      if ( element != -1 )
27         cout << "Found value in element " << element << endl;
28      else
29         cout << "Value not found" << endl;
30
31      return 0; // indicates successful termination
32   } // end main
33
34   // compare key to every element of array until location is     
35   // found or until end of array is reached; return subscript of 
36   // element if key or -1 if key not found                       
37   int linearSearch( const int array[], int key, int sizeOfArray )
38   {                                                              
39      for ( int j = 0; j < sizeOfArray; j++ )                     
40         if ( array[ j ] == key ) // if found,                    
41            return j; // return location of key                   
42                                                                  
43      return -1; // key not found                                 
44   } // end function linearSearch

Enter integer search key: 36
Found value in element 18

Enter integer search key: 37
Value not found

The linear searching method works well for small arrays or for unsorted arrays (i.e., arrays whose elements are in no particular order). However, for large arrays, linear searching is inefficient.