arrays - read - Ruby 2.0.0 Array#bsearch comportamiento

ruby object key value

Question

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

Answer 1

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 <=> .

Answer 2

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;)