Searching and Hashing

It is important to understand what search is and when it is appropriate. This page explains sequential and binary search, and their implementation. There is also the matter of hashing as a storage and search technique. In so doing, we introduce the unordered map and how to implement a map abstract data type using hashing. Read Sections 6.1-6.5. You may also find Sections 6.6-6.11 useful for practice.

4. The Binary Search

It is possible to take greater advantage of the ordered vector if we are clever with our comparisons. In the sequential search, when we compare against the first item, there are at most $n - 1$

more items to look through if the first item is not what we are looking for. Instead of searching the vector in sequence, a binary search will start by examining the middle item. If that item is the one we are searching for, we are done. If it is not the correct item, we can use the ordered nature of the vector to eliminate half of the remaining items. If the item we are searching for is greater than the middle item, we know that the entire lower half of the vector as well as the middle item can be eliminated from further consideration. The item, if it is in the vector, must be in the upper half.

We can then repeat the process with the upper half. Start at the middle item and compare it against what we are looking for. Again, we either find it or split the vector in half, therefore eliminating another large part of our possible search space. Figure 3 shows how this algorithm can quickly find the value 54. The complete function is shown in CodeLens 3.

../_images/binsearch.png

Figure 3: Binary Search of an Ordered vector of Integers

 #include <iostream>
#include <vector>
using namespace std;

// Checks to see if item is in a vector
// retruns true or false (1 or 0)
// using binary Search
bool
binarySearch(vector<int> avector, int item) {
    int first = 0;
    int last = avector.size() - 1;
    bool found = false;

    while (first <= last && !found)
{
        int midpoint = (first + last) / 2;
        if (avector[midpoint] == item) {
            found = true;
       
} else {
            if (item < avector[midpoint]) {
                last = midpoint - 1;
           
} else {
                first = midpoint + 1;
            }
        }
   
}
    return found;
}

int main() {
    // Using static array to initialize a vector
    static const int arr[] = {0, 1, 2, 8, 13, 17, 19, 32, 42};
    vector<int>
avector(arr, arr + sizeof(arr) / sizeof(arr[0]));

    cout << binarySearch(avector, 3) << endl;
    cout << binarySearch(avector, 13) << endl;

    return 0;
}

Before we move on to the analysis, we should note that this algorithm is a great example of a divide and conquer strategy. Divide and conquer means that we divide the problem into smaller pieces, solve the smaller pieces in some way, and then reassemble the whole problem to get the result. When we perform a binary search of a list, we first check the middle item. If the item we are searching for is less than the middle item, we can simply perform a binary search of the left half of the original list. Likewise, if the item is greater, we can perform a binary search of the right half. Either way, this is a recursive call to the binary search function passing a smaller list. CodeLens 4 shows this recursive version.

There is a vector initializer within C++ that can be used much like python slices, however this can only be used when new vectors are created.

#include <iostream>
#include <vector>
using namespace std;

 // Checks to see if item is in a vector
 // retruns true or false (1 or 0)
 // using binary Search and
 // seperating the vector in halves

bool binarySearch(vector<int> alist, int item) {
      if (alist.size() == 0) {
              return false;
      } else {
              int midpoint = alist.size() / 2;
              if (alist[midpoint] == item) {
                      return true;
              } else {
                      if (item < alist[midpoint]) {
                              vector<int> lefthalf(alist.begin(), alist.begin() + midpoint);
                              return binarySearch(lefthalf, item);
                      } else {
                              vector<int> righthalf(
                                      alist.begin() + midpoint + 1, alist.end());
                              return binarySearch(righthalf, item);
                      }
              }
      }
}

int main() {
      // Using static array to initialize a vector
      static const int arr[] = {0, 1, 2, 8, 13, 17, 19, 32, 42};
      vector<int> alist(arr, arr + sizeof(arr) / sizeof(arr[0]));

      cout << binarySearch(alist, 3) << endl;
      cout << binarySearch(alist, 13) << endl;

      return 0;
}

A Recursive Binary Search (binary_search_cpp_recursive)