Двоичный поиск

Некоторые методы 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]