# Binary search (C Plus Plus)

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<typenameT,typenamecompare_less >intarray_binary_search(T a[],intlow,inthigh, T target){while(low <= high){intmiddle = low + (high - low)/2;if(compare_less(target, a[middle])) high = middle - 1;elseif(compare_less(a[middle], target)) low = middle + 1;elsereturnmiddle;}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.

<<generic binary search>>=template<typenameT,typenameIterT,typenamecompare_less > IterT generic_binary_search(IterT begin, IterT end, T target){IterT initial_end = end;while(begin < end){IterT middle = begin + (end - begin - 1)/2;if(compare_less(target, *middle)) end = middle;elseif(compare_less(*middle, target)) begin = middle + 1;elsereturnmiddle;}returninitial_end;}

For convenience, we supply an overload that doesn't take a comparison operator, just using "<". We can't use `std::less`

because C++ doesn't support default template parameters on functions:

<<generic binary search with two template arguments>>=template<typenameT,typenameIterT > IterT generic_binary_search(IterT begin, IterT end, T target){IterT initial_end = end;while(begin < end){IterT middle = begin + (end - begin - 1)/2;if(target < *middle) end = middle;elseif(*middle < target) begin = middle + 1;elsereturnmiddle;}returninitial_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 <iostream>#include <vector>#include <cstdlib> // atoigeneric binary search generic binary search with two template argumentsintmain(intargc,char* argv[]){intnum_elements = std::atoi(argv[1]);int* a =newint[num_elements]; std::vector<int> v;for(inti=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());{intpresent_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");}}{intpresent_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");}return0;}

Download code |