我注意到,从
Ruby 2.0.0开始,数组类有一个我正在测试的bsearch方法,我没有得到我期望的行为.为什么它返回2和5的值,但对于-1,1和4返回零？
arr_in = [-1,1,2,4,5]
arr_in.bsearch { |x| x == 3 } #=> nil
arr_in.bsearch { |x| x == -1 } #=> nil
arr_in.bsearch { |x| x == 1 } #=> nil
arr_in.bsearch { |x| x == 2 } #=> 2
arr_in.bsearch { |x| x == 4 } #=> nil
arr_in.bsearch { |x| x == 5 } #=> 5
解决方法
arr_in = [-1,5]
arr_in.bsearch{ |x| 2 - x }
#=> 2
arr_in.bsearch{ |x| -1 - x }
#=> -1
arr_in.bsearch{ |x| 3 - x }
#=> nil
二进制搜索使用块的结果作为提示,应选择阵列的哪一部分(左侧或右侧)用于在下一次迭代中进行搜索.如果块返回0,它将停止搜索.如果它返回少于0,它会走到左边,否则它是正确的:)
更多信息在这里
http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch
UPD
好的,让我们举个例子
arr_in = [-1,5]
arr_in.bsearch { |x| x == 3 }
首先,我们将中间元素(2)并将其输出到块中. 2 == 3将返回false,所以我们移动到数组的右侧.
我们取[5,5]的中间元素,5和5 == 3是假的
右边没有任何元素,所以我们将返回零
arr_in = [-1,5]
arr_in.bsearch { |x| x == 2 }
前2 == 2是真的.我们去左边
[-1,1]的中间元素是1. 1 == 2是假的.我们去右边
在[-1,1]中没有任何元素到1,所以我们返回最后一个返回true的元素,它是2
PS：别忘了,该数组应该被排序;)