Searching Algorithms
Looking up a phone number, accessing a Web site and checking the definition of a word in a dictionary all involve searching large amounts of data. Searching algorithms all accomplish the same goalfinding an element that matches a given search key, if such an element does, in fact, exist. There are, however, a number of things that differentiate search algorithms from one another. The major difference is the amount of effort they require to complete the search. One way to describe this effort is with Big O notation. For searching and sorting algorithms, this is particularly dependent on the number of data elements.
In Chapter 7, we discussed the linear search algorithm, which is a simple and easy-to-implement searching algorithm. We will now discuss the efficiency of the linear search algorithm as measured by Big O notation. Then, we will introduce a searching algorithm that is relatively efficient but more complex and difficult to implement.
20.2.1. Efficiency of Linear Search
Suppose an algorithm simply tests whether the first element of a vector is equal to the second element of the vector. If the vector has 10 elements, this algorithm requires one comparison. If the vector has 1000 elements, the algorithm still requires one comparison. In fact, the algorithm is completely independent of the number of elements in the vector. This algorithm is said to have a constant runtime, which is represented in Big O notation as O(1). An algorithm that is O(1) does not necessarily require only one comparison. O(1) just means that the number of comparisons is constantit does not grow as the size of the vector increases. An algorithm that tests whether the first element of a vector is equal to any of the next three elements will always require three comparisons, but in Big O notation it is considered O(1). O(1) is often pronounced "on the order of 1" or more simply "order 1."
An algorithm that tests whether the first element of a vector is equal to any of the other elements of the vector requires at most n 1 comparisons, where n is the number of elements in the vector. If the vector has 10 elements, this algorithm requires up to nine comparisons. If the vector has 1000 elements, this algorithm requires up to 999 comparisons. As n grows larger, the n part of the expression "dominates," and subtracting one becomes inconsequential. Big O is designed to highlight these dominant terms and ignore terms that become unimportant as n grows. For this reason, an algorithm that requires a total of n 1 comparisons (such as the one we described in this paragraph) is said to be O(n). An O(n) algorithm is referred to as having a linear runtime. O(n) is often pronounced "on the order of n" or more simply "order n."
Now suppose you have an algorithm that tests whether any element of a vector is duplicated elsewhere in the vector. The first element must be compared with every other element in the vector. The second element must be compared with every other element except the first (it was already compared to the first). The third element must be compared with every other element except the first two. In the end, this algorithm will end up making (n 1) + (n 2) + ... + 2 + 1 or n2/2 n/2 comparisons. As n increases, the n2 term dominates and the n term becomes inconsequential. Again, Big O notation highlights the n2 term, leaving n2/2. As we will soon see, however, constant factors are omitted in Big O notation.
Big O is concerned with how an algorithm's runtime grows in relation to the number of items processed. Suppose an algorithm requires n2 comparisons. With four elements, the algorithm will require 16 comparisons; with eight elements, 64 comparisons. With this algorithm, doubling the number of elements quadruples the number of comparisons. Consider a similar algorithm requiring n2/2 comparisons. With four elements, the algorithm will require eight comparisons; with eight elements, 32 comparisons. Again, doubling the number of elements quadruples the number of comparisons. Both of these algorithms grow as the square of n, so Big O ignores the constant, and both algorithms are considered to be O(n2), which is referred to as quadratic runtime and pronounced "on the order of n-squared" or more simply "order n-squared."
When n is small, O(n2) algorithms (running on today's billion-operation-per-second personal computers) will not noticeably affect performance. But as n grows, you will start to notice the performance degradation. An O(n2) algorithm running on a million-element vector would require a trillion "operations" (where each could actually require several machine instructions to execute). This could require a few hours to execute. A billion-element vector would require a quintillion operations, a number so large that the algorithm could take decades! O(n2) algorithms are easy to write, as you have seen in previous chapters. In this chapter, you will see algorithms with more favorable Big O measures. These efficient algorithms often take a bit more cleverness and effort to create, but their superior performance can be well worth the extra effort, especially as n gets large and as algorithms are compounded into larger programs.
The linear search algorithm runs in O(n) time. The worst case in this algorithm is that every element must be checked to determine whether the search key exists in the vector. If the size of the vector is doubled, the number of comparisons that the algorithm must perform is also doubled. Note that linear search can provide outstanding performance if the element matching the search key happens to be at or near the front of the vector. But we seek algorithms that perform well, on average, across all searches, including those where the element matching the search key is near the end of the vector.
Linear search is the easiest search algorithm to implement, but it can be slow compared to other search algorithms. If a program needs to perform many searches on large vectors, it may be better to implement a different, more efficient algorithm, such as the binary search which we present in the next section.
Performance Tip 20.1
|
Sometimes the simplest algorithms perform poorly. Their virtue is that they are easy to program, test and debug. Sometimes more complex algorithms are required to realize maximum performance. |
20.2.2. Binary Search
The binary search algorithm is more efficient than the linear search algorithm, but it requires that the vector first be sorted. This is only worthwhile when the vector, once sorted, will be searched a great many timesor when the searching application has stringent performance requirements. The first iteration of this algorithm tests the middle element in the vector. If this matches the search key, the algorithm ends. Assuming the vector is sorted in ascending order, then if the search key is less than the middle element, the search key cannot match any element in the second half of the vector and the algorithm continues with only the first half of the vector (i.e., the first element up to, but not including, the middle element). If the search key is greater than the middle element, the search key cannot match any element in the first half of the vector and the algorithm continues with only the second half of the vector (i.e., the element after the middle element through the last element). Each iteration tests the middle value of the remaining portion of the vector. If the element does not match the search key, the algorithm eliminates half of the remaining elements. The algorithm ends either by finding an element that matches the search key or by reducing the subvector to zero size.
As an example, consider the sorted 15-element vector
2 3 5 10 27 30 34 51 56 65 77 81 82 93 99
and a search key of 65. A program implementing the binary search algorithm would first check whether 51 is the search key (because 51 is the middle element of the vector). The search key (65) is larger than 51, so 51 is discarded along with the first half of the vector (all elements smaller than 51.) Next, the algorithm checks whether 81 (the middle element of the remainder of the vector) matches the search key. The search key (65) is smaller than 81, so 81 is discarded along with the elements larger than 81. After just two tests, the algorithm has narrowed the number of elements to check to three (56, 65 and 77). The algorithm then checks 65 (which indeed matches the search key), and returns the index (9) of the vector element containing 65. In this case, the algorithm required just three comparisons to determine whether an element of the vector matched the search key. Using a linear search algorithm would have required 10 comparisons. [Note: In this example, we have chosen to use a vector with 15 elements, so that there will always be an obvious middle element in the vector. With an even number of elements, the middle of the vector lies between two elements. We implement the algorithm to choose the larger of those two elements.]
Figures 20.220.3 define class BinarySearch and its member functions respectively. Class BinarySearch is similar to LinearSearch (Section 7.7)it has a constructor, a search function (binarySearch), a displayElements function, two private data members and a private utility function (displaySubElements). Lines 1828 of Fig. 20.3 define the constructor. After initializing the vector with random ints from 1099 (lines 2425), line 27 calls the Standard Library function sort on the vector data. Function sort takes two random-access iterators and sorts the elements in vector data in ascending order. A random-access iterator is an iterator that allows access to any data item in the vector at any time. In this case, we use data.begin() and data.end() to encompass the entire vector. Recall that the binary search algorithm will work only on a sorted vector.
Figure 20.2. BinarySearch class definition.
(This item is displayed on page 980 in the print version)
|
1 // Fig 20.2: BinarySearch.h 2 // Class that contains a vector of random integers and a function 3 // that uses binary search to find an integer. 4 #include 5 using std::vector; 6 7 class BinarySearch 8 { 9 public: 10 BinarySearch( int ); // constructor initializes vector 11 int binarySearch( int ) const; // perform a binary search on vector 12 void displayElements() const; // display vector elements 13 private: 14 int size; // vector size 15 vector< int > data; // vector of ints 16 void displaySubElements( int, int ) const; // display range of values 17 }; // end class BinarySearch |
Figure 20.3. BinarySearch class member-function definition.
(This item is displayed on pages 980 - 981 in the print version)
|
1 // Fig 20.3: BinarySearch.cpp 2 // BinarySearch class member-function definition. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include // prototypes for functions srand and rand 8 using std::rand; 9 using std::srand; 10 11 #include // prototype for function time 12 using std::time; 13 14 #include // prototype for sort function 15 #include "BinarySearch.h" // class BinarySearch definition 16 17 // constructor initializes vector with random ints and sorts the vector 18 BinarySearch::BinarySearch( int vectorSize ) 19 { 20 size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize 21 srand( time( 0 ) ); // seed using current time 22 23 // fill vector with random ints in range 10-99 24 for ( int i = 0; i < size; i++ ) 25 data.push_back( 10 + rand() % 90 ); // 10-99 26 27 std::sort( data.begin(), data.end() ); // sort the data 28 } // end BinarySearch constructor 29 30 // perform a binary search on the data 31 int BinarySearch::binarySearch( int searchElement ) const 32 { 33 int low = 0; // low end of the search area 34 int high = size - 1; // high end of the search area 35 int middle = ( low + high + 1 ) / 2; // middle element 36 int location = -1; // return value; -1 if not found 37 38 do // loop to search for element 39 { 40 // print remaining elements of vector to be searched 41 displaySubElements( low, high ); 42 43 // output spaces for alignment 44 for ( int i = 0; i < middle; i++ ) 45 cout << " "; 46 47 cout << " * " << endl; // indicate current middle 48 49 // if the element is found at the middle 50 if ( searchElement == data[ middle ] ) 51 location = middle; // location is the current middle 52 else if ( searchElement < data[ middle ] ) // middle is too high 53 high = middle - 1; // eliminate the higher half 54 else // middle element is too low 55 low = middle + 1; // eliminate the lower half 56 57 middle = ( low + high + 1 ) / 2; // recalculate the middle 58 } while ( ( low <= high ) && ( location == -1 ) ); 59 60 return location; // return location of search key 61 } // end function binarySearch 62 63 // display values in vector 64 void BinarySearch::displayElements() const 65 { 66 displaySubElements( 0, size - 1 ); 67 } // end function displayElements 68 69 // display certain values in vector 70 void BinarySearch::displaySubElements( int low, int high ) const 71 { 72 for ( int i = 0; i < low; i++ ) // output spaces for alignment 73 cout << " "; 74 75 for ( int i = low; i <= high; i++ ) // output elements left in vector 76 cout << data[ i ] << " "; 77 78 cout << endl; 79 } // end function displaySubElements |
Lines 3161 define function binarySearch. The search key is passed into parameter searchElement (line 31). Lines 3335 calculate the low end index, high end index and middle index of the portion of the vector that the program is currently searching. At the beginning of the function, the low end is 0, the high end is the size of the vector minus 1 and the middle is the average of these two values. Line 36 initializes the location of the found element to -1the value that will be returned if the search key is not found. Lines 3858 loop until low is greater than high (this occurs when the element is not found) or location does not equal -1 (indicating that the search key was found). Line 50 tests whether the value in the middle element is equal to searchElement. If this is TRue, line 51 assigns middle to location. Then the loop terminates and location is returned to the caller. Each iteration of the loop tests a single value (line 50) and eliminates half of the remaining values in the vector (line 53 or 55).
Lines 2541 of Fig. 20.4 loop until the user enters the value -1. For each other number the user enters, the program performs a binary search on the data to determine whether it matches an element in the vector. The first line of output from this program is the vector of ints, in increasing order. When the user instructs the program to search for 38, the program first tests the middle element, which is 67 (as indicated by *). The search key is less than 67, so the program eliminates the second half of the vector and tests the middle element from the first half of the vector. The search key equals 38, so the program returns the index 3.
Figure 20.4. BinarySearch test program.
(This item is displayed on pages 983 - 984 in the print version)
|
1 // Fig 20.4: Fig20_04.cpp 2 // BinarySearch test program. 3 #include 4 using std::cin; 5 using std::cout; 6 using std::endl; 7 8 #include "BinarySearch.h" // class BinarySearch definition 9 10 int main() 11 { 12 int searchInt; // search key 13 int position; // location of search key in vector 14 15 // create vector and output it 16 BinarySearch searchVector ( 15 ); 17 searchVector.displayElements(); 18 19 // get input from user 20 cout << " Please enter an integer value (-1 to quit): "; 21 cin >> searchInt; // read an int from user 22 cout << endl; 23 24 // repeatedly input an integer; -1 terminates the program 25 while ( searchInt != -1 ) 26 { 27 // use binary search to try to find integer 28 position = searchVector.binarySearch( searchInt ); 29 30 // return value of -1 indicates integer was not found 31 if ( position == -1 ) 32 cout << "The integer " << searchInt << " was not found. "; 33 else 34 cout << "The integer " << searchInt 35 << " was found in position " << position << ". "; 36 37 // get input from user 38 cout << " Please enter an integer value (-1 to quit): "; 39 cin >> searchInt; // read an int from user 40 cout << endl; 41 } // end while 42 43 return 0; 44 } // end main
|
Efficiency of Binary Search
In the worst-case scenario, searching a sorted vector of 1023 elements will take only 10 comparisons when using a binary search. Repeatedly dividing 1023 by 2 (because, after each comparison, we are able to eliminate half of the vector) and rounding down (because we also remove the middle element) yields the values 511, 255, 127, 63, 31, 15, 7, 3, 1 and 0. The number 1023 (210 1) is divided by 2 only 10 times to get the value 0, which indicates that there are no more elements to test. Dividing by 2 is equivalent to one comparison in the binary search algorithm. Thus, a vector of 1,048,575 (220 1) elements takes a maximum of 20 comparisons to find the key, and a vector of over one billion elements takes a maximum of 30 comparisons to find the key. This is a tremendous improvement in performance over the linear search. For a one-billion-element vector, this is a difference between an average of 500 million comparisons for the linear search and a maximum of only 30 comparisons for the binary search! The maximum number of comparisons needed for the binary search of any sorted vector is the exponent of the first power of 2 greater than the number of elements in the vector, which is represented as log2 n. All logarithms grow at roughly the same rate, so in Big O notation the base can be omitted. This results in a Big O of O(log n) for a binary search, which is also known as logarithmic runtime and pronounced "on the order of log n" or more simply "order log n."