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. Exercise 7.33 at the end of this chapter asks you to implement a recursive version of the linear search. In Chapter 20, Searching and Sorting, we present the more complex, yet more efficient, binary search.

Linear Search

The linear search (Fig. 7.19, lines 3744) 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 in the array.

Figure 7.19. Linear search of an array.

(This item is displayed on pages 358 - 359 in the print version)

 1 // Fig. 7.19: fig07_19.cpp
 2 // Linear search of an array.
 3 #include 
 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. If the array is sorted (e.g., its elements are in ascending order), you can use the high-speed binary search technique that you will learn about in Chapter 20, Searching and Sorting.

Introduction to Computers, the Internet and World Wide Web

Introduction to C++ Programming

Introduction to Classes and Objects

Control Statements: Part 1

Control Statements: Part 2

Functions and an Introduction to Recursion

Arrays and Vectors

Pointers and Pointer-Based Strings

Classes: A Deeper Look, Part 1

Classes: A Deeper Look, Part 2

Operator Overloading; String and Array Objects

Object-Oriented Programming: Inheritance

Object-Oriented Programming: Polymorphism

Templates

Stream Input/Output

Exception Handling

File Processing

Class string and String Stream Processing

Web Programming

Searching and Sorting

Data Structures

Bits, Characters, C-Strings and structs

Standard Template Library (STL)

Other Topics

Appendix A. Operator Precedence and Associativity Chart

Appendix B. ASCII Character Set

Appendix C. Fundamental Types

Appendix D. Number Systems

Appendix E. C Legacy Code Topics

Appendix F. Preprocessor

Appendix G. ATM Case Study Code

Appendix H. UML 2: Additional Diagram Types

Appendix I. C++ Internet and Web Resources

Appendix J. Introduction to XHTML

Appendix K. XHTML Special Characters

Appendix L. Using the Visual Studio .NET Debugger

Appendix M. Using the GNU C++ Debugger

Bibliography



C++ How to Program
C++ How to Program (5th Edition)
ISBN: 0131857576
EAN: 2147483647
Year: 2004
Pages: 627

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net