二分查找

一些 Ruby 方法支持在集合中进行二分查找。

Array#bsearch: 通过给定的块，以二分查找的方式返回一个选定的元素。
Array#bsearch_index: 通过给定的块，以二分查找的方式返回一个选定元素的索引。
Range#bsearch: 通过给定的块，以二分查找的方式返回一个选定的元素。

如果未提供块，这些方法都会返回一个枚举器。

给定一个块，这些方法中的每一个都会以二分查找的方式，从 self 中返回一个元素（或元素的索引）。该搜索能在 O(log n) 次操作内找到满足给定条件的 self 中的元素，其中 n 是元素的数量。self 应该是有序的，但这不会被检查。

有两种搜索模式

查找最小值模式: 方法 bsearch 返回第一个使块返回 true 的元素；块必须返回 true 或 false。
查找任意模式: 方法 bsearch 返回一个（如果存在）使块返回零的元素。块必须返回一个数值。

块不应混合模式，即不要有时返回 true 或 false，有时又返回数值，但这不会被检查。

查找最小值模式

在查找最小值模式下，块必须返回 true 或 false。更进一步的要求（但不会被检查）是，不存在索引 i 和 j 使得

0 <= i < j <= self.size.
块为 self[i] 返回 true，为 self[j] 返回 false。

非正式地说：块是这样的，所有求值为 false 的元素都 precedes 所有求值为 true 的元素。

在查找最小值模式下，方法 bsearch 返回第一个使块返回 true 的元素。

示例

a = [0, 4, 7, 10, 12]
a.bsearch {|x| x >= 4 } # => 4
a.bsearch {|x| x >= 6 } # => 7
a.bsearch {|x| x >= -1 } # => 0
a.bsearch {|x| x >= 100 } # => nil

r = (0...a.size)
r.bsearch {|i| a[i] >= 4 } #=> 1
r.bsearch {|i| a[i] >= 6 } #=> 2
r.bsearch {|i| a[i] >= 8 } #=> 3
r.bsearch {|i| a[i] >= 100 } #=> nil
r = (0.0...Float::INFINITY)
r.bsearch {|x| Math.log(x) >= 0 } #=> 1.0

这些块在查找最小值模式下是有意义的

a = [0, 4, 7, 10, 12]
a.map {|x| x >= 4 } # => [false, true, true, true, true]
a.map {|x| x >= 6 } # => [false, false, true, true, true]
a.map {|x| x >= -1 } # => [true, true, true, true, true]
a.map {|x| x >= 100 } # => [false, false, false, false, false]

这没有意义

a.map {|x| x == 7 } # => [false, false, true, false, false]

查找任意模式

在查找任意模式下，块必须返回一个数值。更进一步的要求（但不会被检查）是，不存在索引 i 和 j 使得

0 <= i < j <= self.size.
块为 self[i] 返回一个负值，为 self[j] 返回一个正值。
块为 self[i] 返回一个负值，为 self[j] 返回零。
块为 self[i] 返回零，为 self[j] 返回一个正值。

非正式地说：块是这样的

所有求值为正的元素都 precedes 所有求值为零的元素。
所有求值为正的元素都 precedes 所有求值为负的元素。
所有求值为零的元素都 precedes 所有求值为负的元素。

在查找任意模式下，方法 bsearch 返回一个使块返回零的元素，如果找不到这样的元素，则返回 nil。

示例

a = [0, 4, 7, 10, 12]
a.bsearch {|element| 7 <=> element } # => 7
a.bsearch {|element| -1 <=> element } # => nil
a.bsearch {|element| 5 <=> element } # => nil
a.bsearch {|element| 15 <=> element } # => nil

a = [0, 100, 100, 100, 200]
r = (0..4)
r.bsearch {|i| 100 - a[i] } #=> 1, 2 or 3
r.bsearch {|i| 300 - a[i] } #=> nil
r.bsearch {|i|  50 - a[i] } #=> nil

这些块在查找任意模式下是有意义的

a = [0, 4, 7, 10, 12]
a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
a.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]

这没有意义

a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]