Почему аргументы std:: binary_search являются передовыми итераторами?

Во время просмотра http://en.cppreference.com/w/cpp/algorithm/binary_search я заметил, что он принимает итератор в качестве аргумента. Теперь я смущен, так как я думал, что это скорее будет итератор с произвольным доступом, поэтому бинарный поиск будет фактически двоичным.

Чтобы удовлетворить мое любопытство, я написал небольшую программу:

#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";
    }
}

Компиляция с помощью gcc 4.7.0 и запуск

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

предоставляет следующие результаты на моей машине:

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

Итак, похоже, что он фактически не выполняет двоичный поиск в перечне. Теперь мои вопросы:

Почему такое запутанное имя?

Почему такой код разрешен?

Почему эта ссылка говорит "Логарифмически на расстоянии между первым и последним"?

Что должен сказать об этом стандарт?

EDIT: теперь код сортирует список перед поиском - глупая ошибка, теперь результаты:

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

И, конечно, еще не логарифмический;)