二元搜尋

一些 Ruby 方法支援在集合中執行二元搜尋

Array#bsearch

傳回一個元素,該元素是透過二元搜尋選取的,由指定的區塊決定。

Array#bsearch_index

傳回一個元素的索引,該元素是透過二元搜尋選取的,由指定的區塊決定。

Range#bsearch

傳回一個元素,該元素是透過二元搜尋選取的,由指定的區塊決定。

如果未提供區塊,這些方法中的每個方法都會傳回一個列舉器。

如果提供了區塊,這些方法中的每個方法都會從 self 傳回一個元素(或元素索引),由二元搜尋決定。搜尋會找出 self 中的一個元素,該元素符合 O(log n) 營運中的特定條件,其中 n 是元素的計數。self 應該已排序,但不會檢查這一點。

有兩種搜尋模式

尋找最小值模式

方法 bsearch 傳回第一個區塊傳回 true 的元素;區塊必須傳回 truefalse

任意尋找模式

方法 bsearch 任意元素,如果有的話,區塊傳回零。區塊必須傳回數字值。

區塊不應混合模式,有時傳回 truefalse,有時傳回數字值,但這不會檢查。

尋找最小值模式

在尋找最小值模式中,區塊必須傳回 truefalse。進一步的要求(雖然沒有檢查)是不存在索引 ij,使得

不太正式的說法:區塊是所有評估為 false 的元素都先於所有評估為 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]

任意尋找模式

在任意尋找模式中,區塊必須傳回數字值。進一步的要求(雖然沒有檢查)是不存在索引 ij,使得

不太正式的說法:區塊是

在任意尋找模式中,方法 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]