在Ruby中是否有内置的二进制搜索？

Question

我正在寻找一个内置的Ruby方法,它具有与index二进制搜索算法相同的功能,因此需要预先排序的数组.

我知道我可以编写自己的实现,但根据" Ruby #index Method VS Binary Search ",索引使用的内置简单迭代搜索比纯Ruby版本的二进制搜索更快,因为内置方法是用C写的.

Ruby是否提供任何进行二进制搜索的内置方法？

Answer 1

Ruby 2.0介绍Array#bsearch和Range#bsearch.

对于Ruby 1.9,你应该研究bsearch和binary_search宝石.其他可能性是使用与数组不同的集合,例如使用rbtree

bsearch在我的backports宝石中,但这是一个纯Ruby版本,因此速度相当慢.需要注意的是一个纯Ruby二进制搜索仍然会比像线性内置搜索速度更快index或include?为足够大的阵列/范围(或昂贵的比较),因为它不是复杂的顺序相同O(log n)VS O(n).

今天要玩它,你可以require 'backports/2.0.0/array/bsearch'或require 'backports/2.0.0/range/bsearch'.

祝好运!

Answer 2

自2011年以来发生了很多变化，在Ruby 2.3中，您可以使用 bsearch_index

https://ruby-doc.org/core-2.3.0/Array.html#method-i-bsearch_index

array.bsearch_index { |val| query <=> val }