Ruby的bsearch find-minimum和find-any行为是什么？

Question

我正在阅读Ruby的bsearch文档。

似乎当该块返回true或false时，然后bsearch使用“ find-minimum”模式进行工作。有最大查找模式吗？

对于以下第3至第5种情况，我不太了解Ruby的bsearch find-minimum行为：

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

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

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

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

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

• 对于第三种情况，为什么找不到20呢？
• 对于第四种情况，为什么也找不到20呢？（第一个小于50）。
• 对于5日的情况下，为什么它找到10，而不是20？

同样，find-any当块不返回true或false而是返回数字时，bsearch似乎将使用该模式。但是我真的无法理解它在文档中的作用：

ary = [0, 4, 7, 10, 12]
# try to find v such that 4 <= v < 8
ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7

像是什么1 - x / 4，它在做什么？

Answer 1

• 对于第三种情况，为什么找不到20呢？
• 对于第四种情况，为什么也找不到20呢？（第一个小于50）。
• 对于5日的情况下，为什么它找到10，而不是20？

您的示例3、4和5违反了该方法的前提条件，因此该方法可以执行所需的任何操作，包括return nil，return 10或格式化硬盘。（尽管最后一个可能性很小。）

该文档指出：

该块必须返回true或false，并且必须有一个索引i（0 <= i <= ary.size），以便：

• 对于索引小于i的任何元素，该块返回false，并且
• 对于任何索引大于或等于i的元素，该块返回true。

您的块违反了该条件，因此该方法可能无法返回有意义的结果。

实际上，让我们逐步介绍Array#bsearch第三个案例的示例运行：

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

在第一次迭代时，算法将选择数组（50）的中间部分，并针对您的代码块进行测试：

50 == 20 #=> false

值false意味着我们正在搜索的元素位于当前元素的右侧。因此，我们要搜索的元素必须在subarray中[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意味着我们正在搜索的元素位于当前元素的右侧。因此，我们要搜索的元素必须在subarray中[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意味着我们正在搜索的元素在当前元素的左侧。因此，我们要搜索的元素必须在subarray中[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。这正是查找任何模式所需要的：正数告诉算法它必须向左看，负数告诉算法必须向右看，零表示“您找到了范围”：

该块必须始终返回一个数字，并且必须有两个索引i和j（0 <= i <= j <= ary.size），以便：

• 如果0 <= k <i，则该块为ary返回一个正数，
• 如果i <= k <j，则该块为ary返回零；并且
• 如果j <= k <ary.size，则该块为ary返回一个负数。