Что такое поиск минимального поиска Ruby и поиск любого поведения?

• Что касается третьего случая, почему он не может найти 20?
• Что касается 4-го случая, почему он также не может найти 20? (первый менее 50).
• В пятом случае, почему он находит 10, а не 20?

Ваши примеры 3, 4 и 5 нарушают предварительное условие метода, поэтому метод может делать все, что захочет, включая возврат nil, возврат 10 или форматирование жесткого диска. (Хотя последнее маловероятно.)

В документации указано, что:

блок должен возвращать true или false, и должен быть индекс i (0 ‹= i ‹= ary.size), чтобы:

• блок возвращает false для любого элемента, индекс которого меньше i, и
• блок возвращает true для любого элемента, индекс которого больше или равен i.

Ваш блок нарушает это условие, поэтому метод не может вернуть осмысленный результат.

Давайте на самом деле рассмотрим пример запуска Array#bsearch для вашего третьего случая:

[10, 20, 50, 80, 110].bsearch{|a| a == 20 }

На первой итерации алгоритм выберет середину массива (50) и проверит ее на вашем блоке:

50 == 20 #=> false

Значение false означает, что искомый элемент находится справа от текущего элемента. Следовательно, искомый элемент должен находиться в подмассиве [80, 110]. Итак, рекурсивно:

[80, 110].bsearch{|a| a == 20 }

Опять же, мы выбираем «средний» элемент (110) и тестируем его на вашем блоке:

110 == 20 #=> false

Поскольку возвращаемое значение блока равно false, мы знаем, что элемент должен быть справа от текущего элемента, но справа больше нет элемента, следовательно, мы знаем, что элемент, который мы ищет, не существует.

Теперь для вашего четвертого случая:

[10, 20, 50, 80, 110].bsearch{|a| a < 50 }

На первой итерации алгоритм выберет середину массива (50) и проверит ее на вашем блоке:

50 < 50 #=> false

Значение false означает, что искомый элемент находится справа от текущего элемента. Следовательно, искомый элемент должен находиться в подмассиве [80, 110]. Итак, рекурсивно:

[80, 110].bsearch{|a| a < 50 }

Опять же, мы выбираем «средний» элемент (110) и тестируем его на вашем блоке:

110 < 50 #=> false

Поскольку возвращаемое значение блока равно false, мы знаем, что элемент должен быть справа от текущего элемента, но справа больше нет элемента, следовательно, мы знаем, что элемент, который мы ищет, не существует.

Пятый случай:

[10, 20, 50, 80, 110].bsearch{|a| a <= 50 }

На первой итерации алгоритм выберет середину массива (50) и проверит ее на вашем блоке:

50 <= 50 #=> true

Значение true означает, что искомый элемент находится слева от текущего элемента. Следовательно, искомый элемент должен находиться в подмассиве [10, 20]. Итак, рекурсивно:

[10, 20].bsearch{|a| a <= 50 }

Опять же, мы выбираем «средний» элемент (20) и тестируем его на вашем блоке:

20 <= 50 #=> true

Итак, элемент все еще должен находиться в левом подмассиве:

[10].bsearch{|a| a <= 50 }

проверит

10 <= 50 #=> true

Поскольку возвращаемое значение блока равно true, мы знаем, что элемент должен быть либо слева от текущего элемента или этого элемента, но справа больше нет элемента, следовательно, мы знаем что элемент, который мы ищем, является этим элементом.

ПРИМЕЧАНИЕ: я предполагал, что Array#bsearch всегда будет выбирать элемент как можно ближе к середине, и я предполагал, что для четного числа элементов всегда будет выбираться один правильный середины. Но вы знаете, что они говорят о предположениях: это делает нас с вами задницами. И действительно, в документации прямо указано:

Не определено, какое значение фактически выбирается на каждой итерации.

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

например, что такое 1 - x / 4 и что он делает?

Это просто ваш критерий поиска. Это 0 для x == 4, положительное для x < 4 и отрицательное для x > 4. Это именно то, что нужно режиму find-any: положительное значение указывает алгоритму, что он должен смотреть влево, отрицательное значение указывает, что алгоритм должен смотреть вправо, а ноль означает, что "вы нашли диапазон":

блок всегда должен возвращать число, и должно быть два индекса i и j (0 ‹= i ‹= j ‹= ary.size), чтобы:

• блок возвращает положительное число для ary, если 0 ‹= k ‹ i,
• блок возвращает ноль для ary, если i ‹= k ‹ j, и
• блок возвращает отрицательное число для ary, если j ‹= k ‹ ary.size.

В вашем третьем примере вы не выполняете одно из требований для режима поиска минимума, а именно, что блок возвращает true для любого значения, которое больше или равно вашему значению поиска.

В третьем случае вы поменяли местами значения, так что вы возвращаете true для малых значений и false для больших значений, что снова приводит к неопределенному поведению.

Точно так же в четвертом случае вы изменили порядок проверки на равенство. Требование методов состоит в том, что блок возвращает true, если искомое значение больше или равно искомому значению, и false, если оно меньше.

В целом, алгоритм bsearch достаточно эффективен, если вы можете выполнить все его требования, а именно, чтобы искомый массив был отсортирован и вы указали подходящий блок. В этом случае он, вероятно, будет более эффективным, чем основной метод find.

Если вам не хватает какого-либо из его требований, вы получите неопределенное поведение и фактически случайные результаты. В этом случае вы, вероятно, получите лучшие результаты, просто используя Enumerable#find который также работает с массивами, хэшами,...

Несмотря на документацию, Array#bsearch не

находит значение из этого массива, которое удовлетворяет заданному условию

Что именно делает этот метод, так это то, что он требует от вас создания такого массива ary и такого блока blk, что

режим поиска минимума

... код ary.map(&blk) должен возвращать массив вроде

[false, false, ..., false, false, true, true, ..., true, true]
#                                 ^^^^

тогда код ary.bsearch(&blk) вернет вам крайний левый элемент массива, который возвращает true вместо bkl.call(element).

найти любой режим

... код ary.map(&blk) должен возвращать массив вроде

[positive, ..., positive, 0, ..., 0, negative, ..., negative]
#                         ^^^^^^^^^

тогда код ary.bsearch(&blk) вернет вам элемент массива first-met-by-bisect-jump, который возвращает 0 для bkl.call(element).

Случаи 3-5:

3. [10, 20, 50, 80, 110].bsearch{|a| a == 20}

не имеет смысла как

[10, 20, 50, 80, 110].map{|a| a == 20}
=> [false, true, false, false, false]

4. [10, 20, 50, 80, 110].bsearch{|a| a < 50}

можно изменить в соответствии с требованиями режима поиска минимума:

[10, 20, 50, 80, 110].reverse.map{|a| a < 50}
=> [false, false, false, true, true]
[10, 20, 50, 80, 110].reverse.bsearch{|a| a < 50}
=> 20

5. [10, 20, 50, 80, 110].bsearch{|a| a <= 50}

можно было бы использовать и reverse:

[10, 20, 50, 80, 110].reverse.bsearch{|a| a <= 50}
=> 50