Tại sao tìm kiếm nhị phân trên danh sách trong Java?

Question

Tôi không chắc tại sao Danh sách dưới dạng cấu trúc dữ liệu chung nên có thuật toán tìm kiếm nhị phân cho danh sách được sắp xếp. Không phải phương thức get chấp nhận chỉ mục đi qua Danh sách theo tuần tự, ít nhất là đối với loại phụ 's subtype LinkedList? Nếu vậy, tôi không thấy bất kỳ lợi thế nào khi sử dụng binarySearch so sánh với so sánh tuần tự cho LinkedList. Tất nhiên trừ khi chúng tôi hạn chế Danh sách là ArrayList, chúng tôi có thể thực hiện tìm kiếm nhị phân với sự tự tin hơn.

Sự hiểu biết của tôi có đúng không? Cảm ơn.

Answer 1

Có nhiều cách để triển khai List. Có ArrayList, LinkedList, CopyOnWriteArrayList, v.v. trong thư viện Java chuẩn và một loạt các triển khai khác ngoài các (VLists, bộ đệm tròn, danh sách nhị thức lệch, extendible arrays, 2-3 finger trees, v.v.). Ý tưởng đằng sau việc cung cấp tìm kiếm nhị phân là trong khi không phải tất cả các triển khai Danh sách đều hỗ trợ truy cập ngẫu nhiên, thì những cái thực hiện sẽ được hưởng lợi từ việc thực hiện tìm kiếm nhị phân chung để các tác giả của mỗi cấu trúc dữ liệu không phải triển khai lại từ đầu. Ví dụ: nếu tôi triển khai cấu trúc danh sách mới có hỗ trợ truy cập ngẫu nhiên, nếu tôi triển khai giao diện Danh sách, tôi có thể tự động tìm kiếm nhị phân có sẵn từ lớp Bộ sưu tập.

Điều thú vị là phương pháp binarySearch được viết sao cho nó nhìn vào loại List và xem liệu nó có thực hiện giao diện RandomAccess trước khi thực sự tìm kiếm nhị phân hay không. Nếu danh sách không thực hiện RandomAccess, thay vì sử dụng tìm kiếm nhị phân chuẩn, phương pháp này sử dụng tìm kiếm nhị phân đã sửa đổi với các trình vòng lặp được đảm bảo tạo ra tối đa các phép so sánh O (n) và O (log n). Ý tưởng là để theo dõi nơi thăm dò cuối cùng đã hạ cánh, sau đó đi bộ về phía trước hoặc phía sau số bước thích hợp để tìm vị trí thăm dò tiếp theo, v.v. Tổng công việc được thực hiện sau đó tối đa là n/2 + n/4 + n/8 + n/16 + ... = 2n, vì vậy trong trường hợp xấu nhất, nó chỉ có hai lần xấu như tìm kiếm tuyến tính xấu nhất.

Tóm lại, việc cung cấp việc triển khai chung binarySearch không phải lúc nào cũng có thể nhanh chóng tìm kiếm Danh sách, nhưng đối với các cấu trúc hỗ trợ truy cập nhanh, nó có thể tạo sự khác biệt lớn và tiết kiệm rất nhiều thời gian thực hiện . Ngoài ra, có sự xuống cấp duyên dáng đối với tìm kiếm nhị phân đã sửa đổi chạy trong thời gian O (n) có nghĩa là việc triển khai sẽ không bao giờ tồi tệ hơn nhiều so với quét tuyến tính chuẩn.

Lý do này tương tự như lý do đằng sau thiết kế của thuật toán C++, hoạt động trên phạm vi chung của các giá trị. Hiệu quả của các thuật toán này có thể tồi tệ hơn nhiều so với phiên bản chuyên biệt của thuật toán trên cơ sở từng dữ liệu, nhưng có phiên bản chung có nghĩa là mọi thùng chứa mới hỗ trợ trình vòng lặp có thể tự động có nhiều chức năng được chỉ định trong giao diện.

Hy vọng điều này sẽ hữu ích!

Answer 2

Có, bạn nói đúng, nếu danh sách không cung cấp quyền truy cập ngẫu nhiên, đó là trường hợp của LinkedList, không có bất kỳ lợi thế nào. Từ javadoc của Collections.binarySearch():

Phương pháp này chạy trong log (n) thời gian cho một danh sách "truy cập ngẫu nhiên" (mà cung cấp gần như liên tục thời gian truy cập vị trí). Nếu danh sách được chỉ định không triển khai giao diện {@link RandomAccess} và lớn, phương pháp này sẽ thực hiện tìm kiếm nhị phân dựa trên vòng lặp thực hiện các phép chuyển giao liên kết O (n) và so sánh phần tử O (log n).

Vì vậy, sự phức tạp trong trường hợp này sẽ giống như trong trường hợp so sánh tuần tự - O (n). Thực tế, tôi tin rằng so sánh tuần tự có thể nhanh hơn trong nhiều trường hợp.