¿Hay una búsqueda binaria incorporada en Ruby?

Question

Estoy buscando un método incorporado de Ruby que tenga la misma funcionalidad que index, pero utiliza un algoritmo de búsqueda binario, y por lo tanto requiere una matriz ordenada previamente.

Sé que podría escribir mi propia implementación, pero de acuerdo con "Ruby#index Method VS Binary Search", la búsqueda iterativa simple incorporada utilizada por el índice es más rápida que una versión pura de Ruby de la búsqueda binaria, ya que el método incorporado está escrito en C.

¿Proporciona Ruby algún método integrado que realice la búsqueda binaria?

Answer 1

Ruby 2.0 presentó Array#bsearch y Range#bsearch.

Para Ruby 1.9, debe buscar en las gemas bsearch y binary_search. Otra posibilidad es utilizar un conjunto diferente de una matriz, como using rbtree

bsearch está en mi backports gem, pero esta es una versión pura de Ruby, por lo que un poco más lento. Tenga en cuenta que una búsqueda binaria pura de Ruby seguirá siendo más rápida que una búsqueda interna lineal como index o include? para matrices/rangos suficientemente grandes (o comparaciones costosas), ya que no es el mismo orden de complejidad O(log n) contra .

Para jugar con él hoy, puede require 'backports/2.0.0/array/bsearch' o require 'backports/2.0.0/range/bsearch'.

¡Buena suerte!

Answer 2

Mucho ha cambiado desde 2011, en Ruby 2.3, puede utilizar bsearch_index

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

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