In this algorithms video, we demonstrate and explain the two most common methods of searching arrays for an element: linear and binary search. The linear search is very simple and works on unsorted arrays of elements. The binary search is slightly more complicated and requires a sorted array of elements, but is much faster.

Below, we have C++ code for the linear and binary search algorithms. The code in the main function creates a sorted array of eight elements. Then outputs the entries. Finally, the linear and binary search algorithms are called for each entry of the array.

#include <iostream>

int LinearSearch(int* ipArray, int iSize, int iTarget) {
    for (int iIndex = 0; iIndex < iSize; ++iIndex) {
        if (ipArray[iIndex] == iTarget) {
            return iIndex;
        }
    }
    return -1;
}

int BinarySearch(int* ipArray, int iSize, int iTarget) {
    int iLow    = 0;
    int iHigh   = iSize;
    while (iLow + 1 < iHigh) {
        // Take the average as the test value
        int iCheck = ((iLow + iHigh) >> 1);
        if (ipArray[iCheck] > iTarget) {
            iHigh   = iCheck;
        } else {
            iLow    = iCheck;
        }
    }
    if (ipArray[iLow] == iTarget) {
        return iLow;
    } else {
        return -1;
    }
}

#define MArraySize 8

int main() {
    using namespace std;

    // Create a sorted array
    int iaArray[MArraySize];
    iaArray[0] = (rand() % 9);
    for (int iIndex = 1; iIndex < MArraySize; ++iIndex) {
        iaArray[iIndex] = iaArray[iIndex - 1] + (rand() % 10) + 1;
    }

    // Output the array
    for (int iIndex = 0; iIndex < MArraySize; ++iIndex) {
        cout << iaArray[iIndex] << "  ";
    }
    cout << endl;

    for (int iIndex = 0; iIndex < MArraySize; ++iIndex) {
        int iTgt = iaArray[iIndex];
        cout << "Linear: " << LinearSearch(iaArray, MArraySize, iTgt)
          << "  Binary: " << BinarySearch(iaArray, MArraySize, iTgt)
          << endl;
    }

    return 0;
}

The output from the C++ code above is shown here:

Speed is a primary consideration of any algorithm. As we stated in the video, the most important speed measure is the average speed since we will typically expect an algorithm to be called repeatedly with random values.

Below, we give code to calculate the average number of comparisons for each search. In this segment, we have added an extra reference argument to capture the number of comparisons for a given call. By calling the search functions with each entry of the array as a target and summing the comparisons and dividing by the array size, we get the average number comparisons. In this case, the array size is 100 but can be set to any size we like by changing the number after MArrraySize.

// Average comparisons for linear and binary search
#include <iostream>

// Linear search with comparison count
int LinearSearch(int* ipArray, int iSize, int iTarget, int& irComp)
{
    irComp = 0;
    for (int iIndex = 0; iIndex < iSize; ++iIndex) {
        ++irComp;
        if (ipArray[iIndex] == iTarget) {
            return iIndex;
        }
    }
    return -1;
}

// Binary search with comparison count
int BinarySearch(int* ipArray, int iSize, int iTarget, int& irComp)
{
    irComp      = 0;
    int iLow    = 0;
    int iHigh   = iSize;
    while (iLow + 1 < iHigh) {
        // Take the average as the test value
        int iCheck = ((iLow + iHigh) >> 1);
        ++irComp;
        if (ipArray[iCheck] > iTarget) {
            iHigh   = iCheck;
        } else {
            iLow    = iCheck;
        }
    }
    ++irComp;
    if (ipArray[iLow] == iTarget) {
        return iLow;
    } else {
        return -1;
    }
}

#define MArraySize 100

int main() {
    using namespace std;

    // Create a sorted array
    int iaArray[MArraySize];
    iaArray[0] = (rand() % 99);
    for (int iIndex = 1; iIndex < MArraySize; ++iIndex) {
        iaArray[iIndex] = iaArray[iIndex - 1] + (rand() % 10) + 1;
    }

    // Calculate the average number of comparisons for each
    double dTotalLinear = 0.0;
    double dTotalBinary = 0.0;
    for (int iIndex = 0; iIndex < MArraySize; ++iIndex) {
        int iTarget = iaArray[iIndex];
        int iCompCount;
        LinearSearch(iaArray, MArraySize, iTarget, iCompCount);
        dTotalLinear += iCompCount;
        BinarySearch(iaArray, MArraySize, iTarget, iCompCount);
        dTotalBinary += iCompCount;
    }
    double dAveLinear = (dTotalLinear/MArraySize);
    double dAveBinary = (dTotalBinary/MArraySize);

    cout << "Array Size = " << MArraySize << endl;
    cout << "Average Linear Comparisons = " << dAveLinear << endl;
    cout << "Average Binary Comparisons = " << dAveBinary << endl;

    return 0;
}

The output of the above program and the average number of comparisons is shown below. As the numbers indicate, the binary search is much faster and gets relatively faster as the size of the array grows. These notions of algorithm speed will be made more rigorous in the coming lessons.

Of course, theses averages do not account for missing or multiple elements. Multiple targets in the array will tend to speed up the linear search while a missing target value requires that the linear search check every element. Neither circumstance affects the binary search, which always requires approximately log base 2 comparisons.