Searching and Hashing

When data items are stored in a container type such as a Python list or a C++ array/vector, we say that they have a linear or sequential relationship. Each data item is stored in a position relative to the others. In Python lists, these relative positions are the index values of the individual items. In C++ arrays, these are simply adjacent memory locations each equally sized to fit the data type of the container. Since these index values are ordered, it is possible for us to visit them in sequence. This process gives rise to our first searching technique, the sequential search.

Figure 1 shows how this search works. Starting at the first item in the list, we simply move from item to item, following the underlying sequential ordering until we either find what we are looking for or run out of items. If we run out of items, we have discovered that the item we were searching for was not present.

Figure 1: Sequential Search of a List of Integers

Both the Python and C++ implementations for this algorithm are shown in CodeLens 1 and ActiveCode 1 respectively. The function needs the list and the item we are looking for and returns a boolean value as to whether it is present. The boolean variable found is initialized to False and is assigned the value True if we discover the item in the list (Or vector, in the case of C++).

xxxxxxxxxx

    vector<int> testvector(arr,arr+(sizeof(arr)/sizeof(arr[0])));

#include <iostream>

#include <vector>

using namespace std;

​

// Checks to see if item is in a vector

// retruns true or false (1 or 0)

//using sequential Search

bool sequentialSearch(vector<int> avector, int item) {

    unsigned int pos = 0;

    bool found = false;

​

    while (pos < avector.size() && !found) {

        if (avector[pos] == item) {

            found = true;

        } else {

            pos++;

        }

    }

​

    return found;

}

​

int main() {

    // Vector initialized using an array