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

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