Có tìm kiếm nhị phân tích hợp trong Ruby không?

Question

Tôi đang tìm một phương thức Ruby tích hợp có chức năng giống như index nhưng sử dụng thuật toán tìm kiếm nhị phân và do đó yêu cầu một mảng được sắp xếp trước.

Tôi biết mình có thể viết triển khai của riêng mình, nhưng theo "Ruby#index Method VS Binary Search", tìm kiếm lặp lại đơn giản được sử dụng bởi chỉ mục nhanh hơn phiên bản tìm kiếm nhị phân thuần túy của Ruby, vì phương pháp tích hợp được viết in C.

Ruby có cung cấp bất kỳ phương pháp tích hợp nào để tìm kiếm nhị phân không?

Answer 1

Ruby 2.0 đã giới thiệu Array#bsearch và Range#bsearch.

Đối với Ruby 1.9, bạn nên xem xét đá quý bsearch và binary_search. Khả năng khác là sử dụng một bộ sưu tập khác nhau hơn so với một mảng, như using rbtree

bsearch được trong backports gem của tôi, nhưng đây là một phiên bản Ruby tinh khiết, vì vậy khá chậm hơn một chút. Lưu ý rằng tìm kiếm nhị phân Ruby thuần túy sẽ vẫn nhanh hơn tìm kiếm nội tuyến tuyến tính như index hoặc include? cho mảng/dải ô đủ lớn (hoặc so sánh đắt tiền), vì nó không theo thứ tự phức tạp như O(log n) và O(n).

Để chơi với nó ngay hôm nay, bạn có thể require 'backports/2.0.0/array/bsearch' hoặc require 'backports/2.0.0/range/bsearch'.

Chúc may mắn!

Answer 2

Rất nhiều đã thay đổi kể từ năm 2011, trong Ruby 2.3, bạn có thể sử dụng bsearch_index

https://ruby-doc.org/core-2.3.0/Array.html#method-i-bsearch_index

array.bsearch_index { |val| query <=> val }