# Algorithms: Linear and Binary Searching

## Linear and Binary Searching

In this algorithms video, we demonstrate and explain the two most common methods of searching arrays for an element: * linear* and

*. The*

**binary search****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.