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

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

• Для self[i] блок возвращает true, а для self[j] — false.

Говоря менее формально: все элементы, для которых блок возвращает 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]