bsearch optimisation dans ruby ​​

Question

J'ai une méthode qui va chercher la première apparition d'un nombre dans un tableau trié et retourner l'indice de ce nombre.

def binary_search_sorted(sorted_array, n) 
    first = 0 
    array.bsearch do |x| 
    if x <= n 
     first = array.find_index(n) 
     break 
    else 
     first = -1 
    end 
    end 
    p first 
end 

binary_search_sorted([1,1,2,3,4,4,5,5,5,5,9], 5) 

Le plus va revenir 6 parce que la première apparition de 5 est à l'indice 6

Est-ce l'utilisation correcte de bsearch? Qu'est-ce qui se passe réellement sous le capot de cette méthode. Comment pourrais-je améliorer la méthode?

Answer 1

Disons que nous jouons "devinez le nombre". J'ai un chiffre entre 0 et 1000 dans mon esprit, il faut le deviner. Je réponds soit "trop ​​bas", "trop ​​haut" ou "c'est tout". Une approche naïve serait: "Est-ce 0?" ("trop ​​bas"), "Est-ce que c'est 1?" etc. Beaucoup plus rapidement serait: "Est-ce 500?" ("trop ​​bas") ; "C'est 750?" etc.

Ce qui est exactement ce que fait bsearch. C'est rapide, mais cela ne marchera que sur les tableaux triés. Il renvoie cependant l'objet recherché, pas son index. Pour récupérer l'index, l'exemple utilise find_index, qui utilise l'approche naïve (est-ce à l'index 0? Est-il à l'index 1? Etc.), ce qui aurait pu être fait sans aller mal avec bsearch en premier lieu. Donc non, ce n'est pas l'utilisation correcte de bsearch. Comme sagarpandya82 commentaires, jetez un oeil à bsearch_index, qui renverra un index.