在Ruby中是否有内置的二进制搜索功能? [英] Is there a built-in binary-search In Ruby?

问题描述

我正在寻找一种内置的Ruby方法，该方法具有与index相同的功能，但是使用二进制搜索算法，因此需要预先排序的数组.

I am looking for a built-in Ruby method that has the same functionality as index but uses a binary search algorithm, and thus requires a pre-sorted array.

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

I know I could write my own implementation, but according to "Ruby#index Method VS Binary Search", the built-in simple iterative search used by index is faster than a pure-Ruby version of binary search, since the built-in method is written in C.

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

Does Ruby provide any built-in methods that do binary search?

推荐答案

Ruby 2.0引入了 和 Range#bsearch .

Ruby 2.0 introduced Array#bsearch and Range#bsearch.

对于Ruby 1.9，您应该查看 bsearch 和使用rbtree

For Ruby 1.9, you should look into the bsearch and binary_search gems. Other possibility is to use a different collection than an array, like using rbtree

bsearch在我的 backports gem 中，但这是一个纯Ruby版本，因此速度要慢很多.请注意，对于足够大的数组/范围(或昂贵的比较)，纯Ruby二进制搜索仍然比index或include?的线性内置搜索要快，因为复杂度O(log n)与.

bsearch is in my backports gem, but this is a pure Ruby version, so quite a bit slower. Note that a pure Ruby binary search will still be faster than a linear builtin search like index or include? for big enough arrays/ranges (or expensive comparisons), since it's not the same order of complexity O(log n) vs O(n).

要立即使用它，您可以require 'backports/2.0.0/array/bsearch'或require 'backports/2.0.0/range/bsearch'.

To play with it today, you can require 'backports/2.0.0/array/bsearch' or require 'backports/2.0.0/range/bsearch'.

祝你好运！

这篇关于在Ruby中是否有内置的二进制搜索功能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！