Binäre Suche

Einige Ruby-Methoden unterstützen die binäre Suche in einer Sammlung

Array#bsearch: Gibt ein Element zurück, das durch eine binäre Suche ausgewählt wurde, wie durch einen gegebenen Block bestimmt.
Array#bsearch_index: Gibt den Index eines Elements zurück, das durch eine binäre Suche ausgewählt wurde, wie durch einen gegebenen Block bestimmt.
Range#bsearch: Gibt ein Element zurück, das durch eine binäre Suche ausgewählt wurde, wie durch einen gegebenen Block bestimmt.

Jede dieser Methoden gibt einen Enumerator zurück, wenn kein Block angegeben wird.

Mit einem Block gibt jede dieser Methoden ein Element (oder den Elementindex) aus self zurück, das durch eine binäre Suche bestimmt wird. Die Suche findet ein Element von self, das die gegebene Bedingung in O(log n) Operationen erfüllt, wobei n die Anzahl der Elemente ist. self sollte sortiert sein, dies wird jedoch nicht überprüft.

Es gibt zwei Suchmodi

Find-Minimum-Modus: Die Methode bsearch gibt das erste Element zurück, für das der Block true zurückgibt; der Block muss true oder false zurückgeben.
Find-Any-Modus: Die Methode bsearch gibt ein beliebiges Element zurück, für das der Block Null zurückgibt. Der Block muss einen numerischen Wert zurückgeben.

Der Block sollte die Modi nicht vermischen, indem er manchmal true oder false und manchmal einen numerischen Wert zurückgibt, dies wird jedoch nicht überprüft.

Find-Minimum-Modus

Im Find-Minimum-Modus muss der Block true oder false zurückgeben. Die weitere Anforderung (obwohl nicht überprüft) ist, dass es keine Indizes i und j gibt, so dass

0 <= i < j <= self.size.
Der Block gibt true für self[i] und false für self[j] zurück.

Weniger formell: Der Block ist so beschaffen, dass alle false-auswertenden Elemente allen true-auswertenden Elementen vorausgehen.

Im Find-Minimum-Modus gibt die Methode bsearch das erste Element zurück, für das der Block true zurückgibt.

Beispiele

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

Diese Blöcke sind im Find-Minimum-Modus sinnvoll

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]

Das wäre nicht sinnvoll

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

Find-Any-Modus

Im Find-Any-Modus muss der Block einen numerischen Wert zurückgeben. Die weitere Anforderung (obwohl nicht überprüft) ist, dass es keine Indizes i und j gibt, so dass

0 <= i < j <= self.size.
Der Block gibt einen negativen Wert für self[i] und einen positiven Wert für self[j] zurück.
Der Block gibt einen negativen Wert für self[i] und Null für self[j] zurück.
Der Block gibt Null für self[i] und einen positiven Wert für self[j] zurück.

Weniger formell: Der Block ist so beschaffen, dass

Alle positiv auswertenden Elemente gehen allen Null auswertenden Elementen voraus.
Alle positiv auswertenden Elemente gehen allen negativ auswertenden Elementen voraus.
Alle Null auswertenden Elemente gehen allen negativ auswertenden Elementen voraus.

Im Find-Any-Modus gibt die Methode bsearch ein beliebiges Element zurück, für das der Block Null zurückgibt, oder nil, wenn kein solches Element gefunden wird.

Beispiele

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

Diese Blöcke sind im Find-Any-Modus sinnvoll

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]

Das wäre nicht sinnvoll

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