二元搜尋¶ ↑
一些 Ruby 方法支援在集合中執行二元搜尋
Array#bsearch
-
傳回一個元素,該元素是透過二元搜尋選取的,由指定的區塊決定。
Array#bsearch_index
-
傳回一個元素的索引,該元素是透過二元搜尋選取的,由指定的區塊決定。
Range#bsearch
-
傳回一個元素,該元素是透過二元搜尋選取的,由指定的區塊決定。
如果未提供區塊,這些方法中的每個方法都會傳回一個列舉器。
如果提供了區塊,這些方法中的每個方法都會從 self
傳回一個元素(或元素索引),由二元搜尋決定。搜尋會找出 self
中的一個元素,該元素符合 O(log n)
營運中的特定條件,其中 n
是元素的計數。self
應該已排序,但不會檢查這一點。
有兩種搜尋模式
- 尋找最小值模式
-
方法
bsearch
傳回第一個區塊傳回true
的元素;區塊必須傳回true
或false
。 - 任意尋找模式
-
方法
bsearch
任意元素,如果有的話,區塊傳回零。區塊必須傳回數字值。
區塊不應混合模式,有時傳回 true
或 false
,有時傳回數字值,但這不會檢查。
尋找最小值模式
在尋找最小值模式中,區塊必須傳回 true
或 false
。進一步的要求(雖然沒有檢查)是不存在索引 i
和 j
,使得
-
0 <= i < j <= self.size
. -
區塊傳回
true
給self[i]
,傳回false
給self[j]
。
不太正式的說法:區塊是所有評估為 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]
任意尋找模式
在任意尋找模式中,區塊必須傳回數字值。進一步的要求(雖然沒有檢查)是不存在索引 i
和 j
,使得
-
0 <= i < j <= self.size
. -
區塊傳回負值給
self[i]
,傳回正值給self[j]
。 -
區塊傳回負值給
self[i]
,傳回零給self[j]
。 -
區塊傳回零給
self[i]
,傳回正值給self[j]
。
不太正式的說法:區塊是
-
所有評估為正值的元素都先於所有評估為零的元素。
-
所有評估為正值的元素都先於所有評估為負值的元素。
-
所有評估為零的元素都先於所有評估為負值的元素。
在任意尋找模式中,方法 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]