Бинарный поиск

Несколько методов 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]