Tại sao các đối số của std :: binary_search là các trình vòng lặp chuyển tiếp?

Question

Trong khi thử sử dụng http://en.cppreference.com/w/cpp/algorithm/binary_search Tôi đã nhận thấy nó cần chuyển tiếp trình lặp làm đối số. Bây giờ tôi đang bối rối, vì tôi nghĩ rằng nó sẽ là một iterator truy cập ngẫu nhiên, do đó, tìm kiếm nhị phân sẽ được thực sự nhị phân.

Để thỏa mãn sự tò mò của tôi, tôi đã viết một chương trình nhỏ:

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

Biên soạn nó với gcc 4.7.0 và chạy

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

cung cấp kết quả như sau trên máy tính của tôi:

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 

Vì vậy, có vẻ như nó không thực sự thực hiện tìm kiếm nhị phân trên danh sách chuyển tiếp. Bây giờ câu hỏi của tôi là:

Tại sao một cái tên khó hiểu như vậy?

Tại sao mã như thế này được phép?

Tại sao tham chiếu cho biết đó là "Lôgarit trong khoảng cách giữa đầu tiên và cuối cùng"?

Tiêu chuẩn phải nói gì về nó?

EDIT: Bây giờ mã sắp xếp các danh sách trước khi tìm kiếm - sai lầm ngu ngốc, bây giờ kết quả là:

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 

Và tất nhiên vẫn không logarit;)

Answer 1

Các tài liệu của việc thực hiện STL SGI gốc , từ đó chuẩn bị xuất phát, states that

số lượng so sánh là logarit: tối đa là log (cuối cùng - lần đầu tiên) + 2. Nếu ForwardIterator là một acce ngẫu nhiên SS Iterator sau đó số lượng các bước thông qua phạm vi cũng là logarit; nếu không, số bước là tỷ lệ thuận với cuối cùng - đầu tiên.

Đó là, số lượng so sánh phải lúc nào cũng logarit, trong khi số lượng tiến bộ, mà bị ảnh hưởng bởi sự thiếu ngẫu nhiên khả năng tiếp cận, có thể là tuyến tính. Trong thực tế, stl::advance có thể được sử dụng, mà độ phức tạp là không đổi nếu iterator là truy cập ngẫu nhiên, tuyến tính khác.

Tìm kiếm nhị phân với số tiến trình lặp tuyến tính, nhưng với số lượng so sánh logarit có ý nghĩa nếu so sánh rất tốn kém. Ví dụ, nếu bạn có một danh sách các đối tượng phức tạp được sắp xếp được sắp xếp, yêu cầu truy cập ổ đĩa hoặc mạng để so sánh, bạn có thể tốt hơn nhiều so với tìm kiếm nhị phân so với tìm kiếm tuyến tính.

Answer 2

Tiêu chuẩn chỉ định thuật toán tìm kiếm được sắp xếp (std::lower_bound(), std::upper_bound() và std::binary_search()) để làm việc trong thời gian tuyến tính cho các trình lặp chuyển tiếp và nhị phân. Để truy cập ngẫu nhiên thời gian là logarit.

Lưu ý rằng số lượng comparisons bị hạn chế là lôgarit, tuy nhiên.

Answer 3

Trái với ("logarit trong distance(first, last)" ví dụ) những gì websites may say, tiêu chuẩn thực sự chỉ nói về so sánh (ví dụ 25.4.3.1, lower_bound):

phức tạp: Tại hầu hết các log2(last − first) + O(1) so sánh

Việc gia tăng của trình lặp là không được bao gồm trong sự phức tạp! Lưu ý rằng thư viện chuẩn yêu cầu tất cả các biến lặp để phân bổ độ phức tạp liên tục, do đó sẽ có chi phí thứ tự O (N) đến từ việc tăng các trình vòng lặp (nhưng có lẽ điều này có một yếu tố hàng đầu rất nhỏ). Trong parti ­ cu ­ lar (25.4.3):

Đối với vòng lặp truy cập không ngẫu nhiên [thuật toán] thực hiện một số tuyến tính của các bước.