Algorithms: Binary Search

Binary search is a classic search algorithm for sorted lists of elements. Below is a simple implementation.

Of course, the STL provides std::binary_search()

Time complexity of Binary Search: log₂N

Some important things to remember for the implementation:

• make sure to base your mid calculation with the lower bound, as below. This is because indexing is from the start of the array, so if you are searching a sub-array that begins beyond index 0, you need to re-base the calculation.
• when searching the sub-array above the middle, you can add 1 to the previous mid value to get the new lower bound value. Similarly, when searching a sub-array below the middle, you can subtract one to get the new higher bound.

#include <iostream>

using namespace std;

/*
 * Binary Search 
 *
 * Params:
 *   data array of type T
 *   size size of the array
 *
 * Returns:
 *   int index where key was found in the array, or
 *   -1 if the key was not found
 */
template<typename T>
int binarySearch(T toFind, T data[], int size) {

    int hi = size, lo = 0, mid = 0;

    while(lo < hi) {
        mid = lo + (hi - lo) / 2; // base you mid calc in lo
        if(toFind == data[mid]) return mid;
        else if(toFind < data[mid]) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1; // not found
}


int main(int argc, char* argv[]) {

    int testData[] = {1,2,3,4,5,6,7,8,9};

    int searchKey = 0;

    int res = binarySearch(searchKey, testData, sizeof(testData) / sizeof(testData[0]));

    if(res == -1)
        cout << "Key not found" << endl;
    else
        cout << "key: " << res << endl;

    return 0;
}

And just for fun, a recursive version…

#include <iostream>

using namespace std;

template<typename T>
int _binarySearch(T toFind, T data[], int lo, int hi) {

    if(lo >= hi)
        return -1;

    int mid = lo + (hi - lo) / 2;

    if(toFind == data[mid]) 
        return mid;
    else if(toFind < data[mid]) 
        return _binarySearch(toFind, data, lo, mid - 1);
    else 
        return _binarySearch(toFind, data, mid + 1, hi);
}

// convenient function to perform BS
template<typename T>
int binarySearch(T toFind, T data[], int size) {
    return _binarySearch(toFind, data, 0, size);
}

int main(int argc, char* argv[]) {

    int testData[] = {1,2,3,4,5,6,7,8,9};

    int searchKey = 3;

    int res = binarySearch(searchKey, testData, sizeof(testData) / sizeof(testData[0]));

    if(res == -1)
        cout << "Key not found" << endl;
    else
        cout << "key: " << res << endl;

    return 0;
}