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

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