紅寶石bsearch優化

Question

我有一個方法，將搜索排序數組中的數字的第一次出現，並返回該數字的索引。

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) 

以上將返回6，因爲5的第一次亮相是在指數6

這是正確的使用bsearch的？這種方法背後實際發生了什麼。我如何改進方法？

Answer 1

說我們在玩「猜數」。我腦海中有一個介於0到1000之間的數字，你必須猜測它。我會回覆「太低」，「太高」或「就是這樣」。 一個幼稚的方法是：「是0嗎？」 （「太低」），「是1？」等等。速度要快得多：「它是500嗎？」 （「太低」） ; 「是750嗎？」等等。

這正是bsearch所做的。速度很快，但它只適用於排序的數組。它返回它所尋找的對象，但不是它的索引。爲了檢索索引，該示例使用find_index，它使用了樸素的方法（它是否處於索引0？它是否處於索引1？等），本來可以在不首先使用bsearch進行智能處理的情況下完成。所以不，這不是bsearch的正確使用。作爲sagarpandya82評論，看看bsearch_index，這將返回一個索引。