Tại sao có Danh sách <T> .BinarySearch (...)?

Question

Tôi đang xem Danh sách và tôi thấy một phương pháp BinarySearch với một số quá tải, và tôi không thể không tự hỏi liệu nó có hợp lý để có một phương thức như vậy trong Danh sách không?

Tại sao tôi muốn thực hiện tìm kiếm nhị phân trừ khi danh sách được sắp xếp? Và nếu danh sách không được sắp xếp, gọi phương thức sẽ chỉ là một sự lãng phí thời gian của CPU. Điểm của phương pháp đó trong Danh sách là gì?

Answer 1

Sắp xếp và tìm kiếm là hai thao tác rất phổ biến trong danh sách. Sẽ không thân thiện khi giới hạn các tùy chọn của nhà phát triển bằng cách không cung cấp tìm kiếm nhị phân trên danh sách thông thường.

Thư viện thiết kế đòi hỏi sự thỏa hiệp - các nhà thiết kế NET đã chọn để cung cấp các chức năng tìm kiếm nhị phân trên cả hai mảng một danh sách trong C# bởi vì họ có khả năng cảm nhận (như tôi) rằng đây là những hoạt động hữu ích và phổ biến, và lập trình viên chọn sử dụng chúng hiểu điều kiện tiên quyết của họ (cụ thể là danh sách được sắp xếp) trước khi gọi chúng.

Thật dễ dàng để sắp xếp một số List<T> sử dụng một trong các quá tải Sort(). Nếu bạn cảm thấy rằng bạn cần một sự bất biến mà người gaurantees phân loại, bạn luôn có thể sử dụng SortedList<TKey,TValue> hoặc SortedSet<T> thay thế.

Answer 2

có nhưng Danh sách có phương thức Sort() để bạn có thể gọi nó trước khi tìm kiếm nhị phân.

Answer 3

Tôi đồng ý hoàn toàn câm khi gọi BinarySearch trên danh sách chưa được phân loại, nhưng nó hoàn hảo nếu bạn biết danh sách lớn của mình được sắp xếp.

Tôi đã sử dụng nó khi kiểm tra xem các mục từ một luồng có tồn tại trong danh sách tĩnh (nhiều hoặc ít hơn) của 100.000 mục trở lên hay không.

Nhị phân Tìm kiếm danh sách là SỐ LƯỢNG nhanh hơn so với thực hiện một danh sách.Tìm, nhiều đơn đặt hàng có cường độ nhanh hơn so với cơ sở dữ liệu tra cứu.

Tôi có ý nghĩa, và tôi rất vui vì điều đó (không phải là khoa học tên lửa sẽ thực hiện nó nếu không).

Answer 4

Những người khác đã chỉ ra rằng BinarySearch khá hữu ích khi được sắp xếp List<T>. Nó không thực sự thuộc về List<T>, mặc dù, như bất cứ ai có kinh nghiệm C + + STL sẽ ngay lập tức nhận ra.

Với sự phát triển ngôn ngữ C# gần đây, việc xác định khái niệm danh sách được sắp xếp (ví dụ: ISortedList<T> : IList<T>) và xác định BinarySearch (et. Al.) Làm phương pháp mở rộng của giao diện đó. Đây là kiểu thiết kế gọn gàng hơn, trực giao hơn.

Tôi đã bắt đầu thực hiện việc đó như một phần của thư viện Nito.Linq. Tôi hy vọng bản phát hành ổn định đầu tiên sẽ diễn ra trong vài tháng tới.

Answer 5

BinarySearch chỉ có ý nghĩa trên một List<T> được sắp xếp, giống như IList<T>.Add chỉ có ý nghĩa đối với một IList<T> với IsReadOnly = false. Đó là lộn xộn, nhưng nó chỉ là một cái gì đó để đối phó với: đôi khi chức năng X phụ thuộc vào tiêu chí Y. Thực tế là Y không phải luôn luôn đúng không làm cho X vô ích.

Bây giờ, trong ý kiến ​​ của tôi, nó là bực bội mà .NET không có chungSort và BinarySearch phương pháp bất kỳIList<T> thực hiện (ví dụ, như là phương pháp mở rộng). Nếu có, chúng tôi có thể dễ dàng sắp xếp các tìm kiếm và cho các mục trong bất kỳ bộ sưu tập không chỉ đọc nào cung cấp quyền truy cập ngẫu nhiên.

Sau đó, một lần nữa, bạn luôn có thể viết của riêng bạn (hoặc copy someone else's).

Answer 6

Tôi lưu ý ngoài các câu trả lời đúng khác mà tìm kiếm nhị phân khó viết một cách đáng ngạc nhiên. Có rất nhiều trường hợp góc và một số số nguyên khôn lanh. Vì tìm kiếm nhị phân rõ ràng là một thao tác phổ biến trên danh sách được sắp xếp, nhóm BCL đã làm cho thế giới một dịch vụ bằng cách viết thuật toán tìm kiếm nhị phân một cách chính xác một lần thay vì khuyến khích khách hàng viết tất cả thuật toán tìm kiếm nhị phân của riêng họ; một số lượng đáng kể các thuật toán do khách hàng tạo ra đó là sai.

Answer 7

Tìm kiếm và sắp xếp là nguyên thủy thuật toán. Nó rất hữu ích cho thư viện chuẩn để triển khai nhanh chóng đáng tin cậy. Nếu không, các nhà phát triển lãng phí thời gian tái phát minh bánh xe.

Tuy nhiên, trong trường hợp của .NET Framework, thật không may rằng các lựa chọn cụ thể của thuật toán xảy ra để làm cho chúng ít hữu ích hơn chúng có thể. Trong một số trường hợp, hành vi của họ không được định nghĩa:

1. List<T>.BinarySearch Nếu danh sách chứa nhiều hơn một phần tử với cùng một giá trị, phương pháp này chỉ trả về một trong những lần xuất hiện, và nó có thể trả lại bất kỳ một trong những lần xuất hiện, không nhất thiết phải là số đầu tiên.

2. List<T> Triển khai này thực hiện một loại không ổn định; tức là, nếu hai phần tử bằng nhau, thì thứ tự của chúng có thể không được giữ nguyên. Ngược lại, một loại ổn định bảo tồn thứ tự các phần tử bằng nhau.

Thật đáng tiếc, vì có các thuật toán xác định nhanh và hữu ích hơn nhiều khi tạo khối. Đáng chú ý là các thuật toán tìm kiếm nhị phân trong Python, Ruby và Go đều tìm thấy phần tử khớp đầu tiên.

Answer 8

Có lẽ một điểm khác là một mảng có thể bằng nhau không được phân loại. Vì vậy, trong lý thuyết, có một BinarySearch trên một mảng có thể là không hợp lệ quá.

Tuy nhiên, như với tất cả các tính năng của một ngôn ngữ cấp cao hơn, chúng cần được áp dụng bởi ai đó có lý do và hiểu dữ liệu hoặc chúng sẽ không thành công. Chắc chắn, một số xuyên kiểm tra có thể được áp dụng, và chúng ta có thể có một lá cờ mà nói "IsSorted" và nó sẽ thất bại trên tìm kiếm nhị phân khác, nhưng .....

Answer 9

Một số mã giả:

if List is sorted 
    use the BinarySearch method 
else if List is not sorted and you think sorting it is "waste of CPU time" 
    use a different algorithm that is more suitable and efficient