Binary search (C Plus Plus)

From LiteratePrograms

Other implementations: C | C++ | Java

Binary search is an algorithm used to quickly locate a particular value in a sorted random-access container, such as a sorted array. It operates by repeatedly narrowing the range of possible locations by examining the element in the middle of this range.

C++ has a template-based binary_search() in its standard library, which is what should normally be used, as well as the function pointer based bsearch inherited from C. A number of simple C implementations that also compile as C++ are described at Binary search (C).

In C++, we can take advantage of templates to easily generalize the C implementation described at Binary search (C) to arrays of any type. We simply replace the element type everywhere by a template parameter "T" and replace "<" by a user-supplied less-than comparison operator.

<<array binary search>>=
template< typename T, typename compare_less >
int array_binary_search(T a[], int low, int high, T target) {
    while (low <= high) {
        int middle = low + (high - low)/2;
        if (compare_less(target, a[middle]))
            high = middle - 1;
        else if (compare_less(a[middle], target))
            low = middle + 1;
        else
            return middle;
    }
    return -1;
}

But we need not stop at arrays — we can generalize the implementation even further to any container permitting random access, such as std::vector. The conventional way of doing this, as done by the standard library's binary_search, is to pass in a begin and end iterator specifying the range. This is very similar to the above implementation, but with the indexes low and high and the return value replaced by iterators. Also, by convention, we make "end" point one past the last element to be searched instead of using an inclusive range, resulting in each instance of "end" being adjusted by 1; if the element is not found we can return the initial value of end, since this is outside the range being searched and so not a normal return value. The optional compare_less parameter can be used to specifiy a custom comparison operation.

<<generic binary search>>=
template< typename T, typename IterT, typename CmpT >
IterT generic_binary_search(IterT begin, IterT end, T target, CmpT compare_less = std::less< T >()) {
    IterT initial_end = end;
    while (begin < end) {
        IterT middle = begin + (end - begin - 1)/2;
        if (compare_less(target, *middle))
            end = middle;
        else if (compare_less(*middle, target))
            begin = middle + 1;
        else
            return middle;
    }
    return initial_end;
}

This simple test code tries out the final binary search on an array and a vector, using std::sort to sort them first:

<<binary_search.cpp>>=
#include <algorithm>
#include <functional> // std::less
#include <iostream>
#include <vector>
#include <cstdlib>  // atoi
generic binary search
int main(int argc, char* argv[]) {
    int num_elements = std::atoi(argv[1]);
    int* a = new int[num_elements];
    std::vector<int> v;
    for(int i=0; i<num_elements; i++) {
        do {
            a[i] = rand() % num_elements;
        } while(a[i] == num_elements/7);
        v.push_back(a[i]);
    }
    std::sort(a, a + num_elements);
    std::sort(v.begin(), v.end());
    {
        int present_val = a[rand() % num_elements];
        int* found_at = generic_binary_search(a, a + num_elements, present_val);
        if (found_at == a + num_elements || *found_at != present_val) {
            puts("ERROR");
        }
    }
    {
        int present_val = v[rand() % num_elements];
        std::vector<int>::iterator found_at =
            generic_binary_search(v.begin(), v.end(), present_val);
        if (found_at == v.end() || *found_at != present_val) {
            puts("ERROR");
        }
    }
    if (generic_binary_search(a, a + num_elements, num_elements/7) != a + num_elements ||
        generic_binary_search(v.begin(), v.end(),  num_elements/7) != v.end())
    {
        puts("ERROR");
    }
    return 0;
}