Блог

У меня есть отсортированный массив number, и я хотел проверить, есть ли number в массиве или нет. Я думаю, что я должен использовать bsearch здесь, но он возвращает nil , даже если число присутствует в массиве, и дает положительный результат только для среднего элемента.

Вот что я тестирую.

 >> [1,2,3,4,5].bsearch { |value| value <=> 1}
>> nil
>> [1,2,3,4,5].bsearch { |value| value <=> 3}
>> 3
  

Я использую Ruby версии 2.3.8

Вы используете Array#bsearch в режиме поиска любого.

Как говорится в документации, ваш блок должен удовлетворять следующим требованиям:

• Все элементы с положительной оценкой предшествуют всем элементам с нулевой оценкой.
• Все элементы с положительной оценкой предшествуют всем элементам с отрицательной оценкой.
• Все элементы с нулевой оценкой предшествуют всем элементам с отрицательной оценкой.

Ваш блок нарушает эти требования.

Давайте рассмотрим пример. На первой итерации Array#bsearch вы выберете средний элемент, который есть 3 , и передадите его вашему блоку. Возвращается ваш блок 1 , что означает, что элемент, который вы ищете, больше 3 и, следовательно, должен быть справа от текущего элемента. Итак, Array#bsearch отбрасывается левая половина массива, и мы остаемся [4, 5] . Теперь снова Array#bsearch выберите «средний» элемент, который есть 4 , и передайте его вашему блоку. Ваш блок возвращает 1 положительное число и, таким образом, означает, что искомый элемент больше 4 и, следовательно, должен находиться в правой половине массива. Итак, снова Array#bsearch отбрасываем левую половину, и мы остаемся [5] . То же самое, Array#bsearch переходит 5 к блоку, ваш блок возвращает 1 положительное число и, таким образом, означает, что нам нужно посмотреть вправо, за исключением того, что мы уже находимся в конце массива, и, таким образом, мы можем сделать вывод, что элемента, который вы ищете, нет в массиве.

Итак, по сути, вы просто говорите Array#bsearch искать не в том месте.

Давайте еще раз посмотрим на документацию:

Они имеют смысл как блоки в режиме поиска любого:

 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 = [0, 4, 7, 10, 12]
a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]
  

Итак, по сути, вы написали свой блок точно так же, как блок, который, как явно указано в документации, является неправильным, и в точности противоположным тому, что указано в документации.

Если вы перевернете два операнда в блоке, чтобы ваш блок выглядел так, как указано в примере в документации, он должен выглядеть, он будет работать:

 [1, 2, 3, 4, 5].bsearch { |value| 0 <=> value } #=> nil
[1, 2, 3, 4, 5].bsearch { |value| 1 <=> value } #=> 1
[1, 2, 3, 4, 5].bsearch { |value| 2 <=> value } #=> 2
[1, 2, 3, 4, 5].bsearch { |value| 3 <=> value } #=> 3
[1, 2, 3, 4, 5].bsearch { |value| 4 <=> value } #=> 4
[1, 2, 3, 4, 5].bsearch { |value| 5 <=> value } #=> 5
[1, 2, 3, 4, 5].bsearch { |value| 6 <=> value } #=> nil