arrays - read - Ruby 2.0.0 Array#bsearch comportamiento
ruby object key value (2)
Noté que a partir de Ruby 2.0.0, la clase array tiene un método bsearch
que estaba probando y no estoy obteniendo el comportamiento que esperaba. ¿Por qué devuelve un valor para 2 y 5 pero nil
para -1, 1 y 4?
arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 3 } #=> nil
arr_in.bsearch { |x| x == -1 } #=> nil
arr_in.bsearch { |x| x == 1 } #=> nil
arr_in.bsearch { |x| x == 2 } #=> 2
arr_in.bsearch { |x| x == 4 } #=> nil
arr_in.bsearch { |x| x == 5 } #=> 5
Me parece más intuitivo utilizar el operador de la nave espacial.
array.bsearch {|x| 3 <=> x }
Solo asegúrate de poner la x
a la derecha de la nave espacial.
Esto también funciona para cadenas y cualquier objeto que sea comparable con <=>
.
arr_in = [-1, 1,2,4,5]
arr_in.bsearch{ |x| 2 - x }
#=> 2
arr_in.bsearch{ |x| -1 - x }
#=> -1
arr_in.bsearch{ |x| 3 - x }
#=> nil
La búsqueda binaria utiliza el resultado del bloque como una sugerencia de qué parte de la matriz (lado izquierdo o derecho) debe elegirse para buscar en la siguiente iteración. Si el bloque devuelve 0, dejará de buscar. Si devuelve menos de 0, irá a la izquierda, de lo contrario, irá a la derecha :)
Más información aquí http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch
UPD
Ok tomemos tu ejemplo
arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 3 }
Primero tomaremos el elemento medio (2) y lo cederemos al bloque. 2 == 3
devolverá false
, por lo que nos movemos hacia el lado derecho de la matriz.
Tomamos el elemento medio de [4, 5]
que es 5
y 5 == 3
es false
No hay ningún elemento a la derecha, por lo que volveremos a nil
arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 2 }
Primero 2 == 2
es true
. Vamos a la izquierda.
El elemento intermedio de [-1, 1]
es 1. 1 == 2
es false
. Vamos a la derecha.
No hay ningún elemento en [-1, 1]
directamente al 1, por lo que devolvemos el último último elemento que devolvió la declaración true
que es 2
PD: no olvides que la matriz debería estar ordenada;)