Обратное выражение в блоке bsearch не работает

Question

ary = [1, 4, 6, 9]
(0...ary.size).bsearch { |i|
  ary[i] - 1
}                                   # => nil

1 - ary[i]                          # => 0

Когда код написан в форме ary[i] - 1 который не работает, как ожидалось.

То, что я пытаюсь сделать, это найти индекс числа 1 в массиве.

Но 1 - ary[i] может вернуть индекс числа правильно. Почему не ary[i] - 1 Работа?

Answer 1

Array#bsearch предназначен для выполнения бинарного поиска, чтобы найти элемент, который соответствует определенным критериям. Согласно документации, если вы возвращаете числовые значения из блока, find-any mode тип поиска используется.

Поиск начинается в центре отсортированного массива - и если блок возвращает отрицательное значение, он продолжает поиск в первой половине, а если блок возвращает положительное значение, он продолжает поиск во второй половине массива.

В вашем случае, когда вы используете ary[i] - 1значение, возвращаемое блоком, всегда положительно, и поиск продолжается рекурсивно во второй половине массива - и никогда не находит значение 1,

Вот код с некоторыми операторами отладки:

ary = [1, 4, 6, 9]
p (0...ary.size).bsearch { |i|
  puts "Elem: #{ary[i]} Index: #{i}"
  ary[i] - 1
}

Выход:

Elem: 4 Index: 1
Elem: 6 Index: 2
Elem: 9 Index: 3
nil
[Finished in 0.4s]    

Answer 2

Array#bsearch возвращает элемент массива, а не индекс соответствующего элемента.

Вы можете использовать Array#index вместо.

Answer 3

Если вы хотите найти индекс элемента вместо самого элемента, вам нужно использовать Array#bsearch_index, Примечание: этот метод был введен в Ruby 2.3, который на момент написания этой статьи еще не был выпущен (он будет выпущен на Рождество 2015 года).

Запрос функции для Array#bsearch_index содержит комментарий Юсуке Эндоха, показывающий, как реализовать Array#bsearch_index (и на самом деле Array#bsearch а также) на основе Range#bsearch:

class Array
  def bsearch_index(&blk)
    return enum_for(__method__) unless blk
    (0...size).bsearch {|i| yield self[i] }
  end
end

Когда вы используете Ruby 2.3 или используете вышеприведенный патч обезьяны, вы можете сделать:

ary.bsearch_index(&1.method(:-))

чтобы найти индекс 1 элемент в вашем массиве.

Причина, почему это не работает с

ary.bsearch_index {|el | el - 1 }

прост: блок нарушает договор bsearch_index (а также bsearch так как они одинаковые). Блок должен возвращать положительное число для индексов слева от того, который вы ищете, отрицательное число для индексов справа от того, который вы ищете, и 0 для индексов в диапазоне, который вы ищете. Ваш блок делает обратное.