Есть встроенный двоичный поиск в Ruby?

Я ищу встроенный Ruby-метод, который имеет ту же функциональность, что и index, но использует алгоритм двоичного поиска и, следовательно, требует предварительно отсортированного массива.

Я знаю, что могу написать свою собственную реализацию, но в соответствии с "Ruby # index Method VS Binary Search", встроенный простой итеративный поиск, используемый индексом, быстрее, чем версия бинарного поиска с чистой рубиной, поскольку встроенный метод написан на C.

Предоставляет ли Ruby какие-либо встроенные методы, которые выполняют двоичный поиск?

Ответ 1

Ruby 2.0 представил Array#bsearch и Range#bsearch.

Для Ruby 1.9 вы должны изучить драгоценные камни bsearch и binary_search. Другая возможность - использовать другую коллекцию, чем массив, например с помощью rbtree

bsearch находится в моем backports gem, но это чистая версия Ruby, поэтому довольно немного медленнее. Обратите внимание: чистый бинарный поиск Ruby будет по-прежнему быстрее, чем линейный встроенный поиск, например index или include? для достаточно больших массивов/диапазонов (или дорогостоящих сравнений), поскольку это не тот же порядок сложности O(log n) vs O(n).

Чтобы играть с ним сегодня, вы можете require 'backports/2.0.0/array/bsearch' или require 'backports/2.0.0/range/bsearch'.

Удачи!

Ответ 2

С 2011 года многое изменилось, в Ruby 2.3 вы можете использовать bsearch_index

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

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