补充一个，http://ruby-china.org/topics/9215

不错，不过那个 bsearch 没看懂，似乎比 select 方便些，但是感觉没有特别大的价值

#2 楼 @fsword bsearch 是针对排序好的进行二分查找吧？

#3 楼 @hooopo 是不是 util.c 里的 c 的二分查找啊？

#2 楼 @fsword 主要价值是性能的提升，对于有序序列，二分查找的平均性能要好的多。

#4 楼 @i5ting 我也不知道哇..........

不知道这两个命名有何深意啊

先前回了一楼，后来发现错了。

我觉得 bsearch 很不直观，暂且不说它的两种使用模式；仅就 find-minimum mode 而言，文档中说要找到 i 元素，要求

• 所有索引小于 i 的元素要使得 block 返回 false
• 所有索引等于或大于 i 的元素要使得 block 返回 true

但是在使用中，

arr = [1,4,7,8,9,13,14,15]

arr.bsearch {|x| x > 3} #=> 4 #正确

但是如果如下使用就很诡异了

arr = [1,4,7,8,9,13] arr.bsearch {|x| x%5 > 3} #=> nil ??

arr = [1,4,7,8,9,13,14,15] arr.bsearch {|x| x%5 > 3} #=> 9 ??

这里 15 似乎不满足条件 2 啊

继续，如果

arr = [1,4,7,8,9,13,15] arr.bsearch {|x| x%5 > 3} #=> nil ??

只是去掉了 14 这个元素，结果就为nil了

太诡异了，难道说 block 里面只能使用>而不能使用%之类的么？

不过这个 bsearch 和 select 不同是肯定的了！

#10 楼 @donnior 二叉树查找，不是遍历，所以只能用值和范围来约束，不能对值进行进一步处理 楼下说的更准确，自宫一下 #8 楼 @luikore 疑惑的就是这个“已排序”，试验了一下，果然是必要条件啊

2.1.0dev :009 > array = [2, 4, 8, 16, 32].shuffle
 => [32, 2, 8, 4, 16] 
2.1.0dev :010 > array.bsearch {|x| x >= 4}       #=> 4
 => 8 
2.1.0dev :011 > array.bsearch {|x| x >= 7}       #=> 8
 => 8 
2.1.0dev :012 > array.bsearch {|x| x >= 9}       #=> 16
 => 16 
2.1.0dev :013 > array.bsearch {|x| x >= 0}       #=> 2
 => 32 
2.1.0dev :014 > array.bsearch {|x| x >= 33}      #=> nil
 => nil 

#10 楼 @donnior

x 在 arr 中是升序的，但 x%5 不是升序的，所以二分查找的条件就不对了

arr = [1,4,7,8,9,13,15]
arr = arr.map{|x| [(x%5), x] }.sort
arr.bsearch {|(x, y)| x > 3}[1]

#10 楼 @donnior 另外用单调函数 + 比较是没问题的

# 单调增
def f x
  x * 2
end
# 单调降
def g x
  -x
end
arr.bsearch {|x| f(x) > 6 }
arr.bsearch {|x| g(x) < -3 }

#11 楼 @fsword #13 楼 @luikore Thanks, 明白了

哇~ 终于可以对 2.0 有一个较全面了解了。

非常感谢~

说起 ko1, 原来他就是写 YARI 那个？? 他的 github 页面刚刚发布了一个基于 ruby2.0 debug API 的 debugger2

https://github.com/ko1/debugger2

#11 楼 @fsword 你测试的例子不太好，没有测出来，其实应该是充分条件。 array = [2, 4, 8, 16, 32].shuffle => [8, 32, 2, 16, 4]

pry(main)> array.bsearch { |x| x > 17 } => nil