ruby bsearch

Array#bsearch

bsearch { |x| ... } -> object | nil

bsearch -> Enumerator

基于块评估结果来判断范围中的每个元素,并且通过二进制搜索来搜索满足条件的值(计算量为O(log n))。如果找不到该元素,则返回nil。Array 必须事先进行排序。

根据块评估的结果,此方法以以下模式之一运行。

  • 查找最小模式
  • 查找任何模式

在最小查找模式下(除非有特殊原因,否则最好使用此模式),条件判断的结果必须如下。

  • 如果所需值是块参数值或上一个元素:返回true
  • 如果所需值是block参数之后的元素:返回false

返回使该块评估为true的第一个元素,或返回nil。

ary = [0471012]
ary.bsearch {| x | x> = 4}#=> 4
ary.bsearch {| x | x> = 6}#=> 7
ary.bsearch {| x | x> = -1}#=> 0
ary.bsearch {| x | x> = 100}#=> nil

查找任何模式都类似于bsearch(3)该块返回类似以下的数字,而非布尔值:假设您要查找的元素位于数组的第i至 j-1个位置。同样,令k为块参数值的索引。

  • 如果块参数值小于期望值范围(0 <= k <i):返回正数
  • 如果块参数值与期望值范围匹配(i <= k <j):返回0
  • 如果块参数值大于期望值范围(j <= k <self.size):返回负数

返回该块对其求值为0或为nil的元素之一:

ary = [0471012]
查找其中#4 <= v <8的元素
ary.bsearch {| x | 1-x / 4}#=> 4或7
查找其中#8 <= v <10的元素
ary.bsearch {| x | 4-x / 2}#=> nil

不要混合使用以上两种模式(确保该块的求值结果总是返回true / false或始终一致的数字)。另外,在二进制搜索的每次迭代中选择值的顺序也没有指定。

如果没有给出块,则返回Enumerator的实例。

[EXCEPTION] TypeError:
当块评估结果不是true,false,nil或数字时,抛出错误
原文地址:https://www.cnblogs.com/itachilee/p/13402462.html