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，它将返回一个索引。