ruby - recursiva - complejidad busqueda binaria

¿Hay una búsqueda binaria incorporada en Ruby?

Question

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

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 index es más rápida que una versión Ruby pura de la búsqueda binaria, ya que el método incorporado está escrito en C.

¿Proporciona Ruby algún método incorporado que realice una búsqueda binaria?

Answer 1

Mucho ha cambiado desde 2011, en Ruby 2.3, puedes usar bsearch_index

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

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

Answer 2

Ruby 2.0 introdujo Array#bsearch y Range#bsearch .

Para Ruby 1.9, debes buscar en las gemas tyler/binary_search y tyler/binary_search . Otra posibilidad es usar una colección diferente a una matriz, como usar rbtree

bsearch está en mi joya de backports , pero esta es una versión pura de Ruby, por lo que es un poco más lenta. ¿Tenga en cuenta que una búsqueda binaria pura de Ruby seguirá siendo más rápida que una búsqueda integrada 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) frente a O(n) .

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

¡Buena suerte!

Answer 3

Yo uso bsearch . Así es como funciona:

array = [''one'', ''two'', ''three'', ''four'', ''five'']
search = array.sort.bsearch { |value| ''four'' <=> value }

Nota: la búsqueda binaria necesita una matriz ordenada; esto agrega una pequeña sobrecarga pero está bien, en comparación con la velocidad de la búsqueda.

search devolverá el valor four de la array , de lo contrario, nil si no encuentra el valor.