Why arguments of std::binary_search are forward iterators?

Question

While perusing http://en.cppreference.com/w/cpp/algorithm/binary_search I've noticed it takes forward iterator as an argument. Now I'm confused, since I thought it would rather be an random access iterator, so the binary search will be actually binary.

To satisfy my curiosity, I've written a little program:

#include <iostream> #include <vector> #include <forward_list> #include <list> #include <deque> #include <algorithm> #include <chrono> #include <random>  int main() {     std::uniform_int_distribution<int> uintdistr(-4000000, 4000000);     std::mt19937 twister(std::chrono::high_resolution_clock::to_time_t(std::chrono::high_resolution_clock::now()));     size_t arr[] = { 200000, 400000, 800000, 1600000, 3200000, 6400000, 12800000 };     for(auto size : arr)     {         std::list<int> my_list;         for(size_t i = 0; i < size; i++)             my_list.push_front(uintdistr(twister));         std::chrono::time_point<std::chrono::high_resolution_clock> start, end;         my_list.sort(); //fixed         start = std::chrono::high_resolution_clock::now();          std::binary_search(my_list.begin(), my_list.end(), 1252525);          end = std::chrono::high_resolution_clock::now();         long long unsigned elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();         std::cout << "Test finished in " << elapsed_time << "\n";     } } 

Compiling it with gcc 4.7.0 and running

g++ -std=c++11 test.cpp 

provides following results on my machine:

Test finished in 0 Test finished in 15625 Test finished in 15625 Test finished in 46875 Test finished in 93750 Test finished in 171875 Test finished in 312500 

So it looks like it doesn't actually do a binary search on a forward list. Now my questions are:

Why such a confusing name?

Why does the code like this allowed?

Why does the reference says it's "Logarithmic in the distance between first and last"?

What does the standard has to say about it?

EDIT: Now the code sorts the list before search - stupid mistake, now the results are:

Test finished in 46875 Test finished in 109375 Test finished in 265625 Test finished in 546875 Test finished in 1156250 Test finished in 2625000 Test finished in 6375000 

And of course still not logarithmic ;)

Answer 1

The docs of the original SGI STL implementation, from which the standard was derived, states that

The number of comparisons is logarithmic: at most log(last - first) + 2. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.

That is, the number of comparisons is always logarithmic, while the number of advancements, which are affected by the lack of random-accessibility, can be linear. In practice, stl::advance is probably used, for which the complexity is constant if the iterator is random access, linear otherwise.

A binary search with a linear number of iterator advancements, but with a logarithmic number of comparisons makes sense if a comparison is very expensive. If, for example, you have a sorted linked-list of complicated objects, which require disk- or network-access to compare, you're probably much better off with a binary search than with a linear one.