2

我正在阅读Ruby 的 bsearch 文档。

似乎当块返回 true 或 false 时，bsearch 使用“find-minimum”模式工作。有没有找到最大值模式？

对于以下第 3 到第 5 种情况，我不太了解 Ruby 的 bsearch 查找最小行为：

[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？
  • 对于第 4 种情况，为什么它也找不到20？（第一个小于 50）。
  • 对于第 5 种情况，为什么它找到10而不是20？

此外，似乎 bsearch 将find-any在块不返回 true 或 false 时使用该模式，而是返回一个数字。但我无法真正理解它在文档中做了什么：

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什么，它在做什么？

4

3 回答 3

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

您的示例 3、4 和 5 违反了该方法的先决条件，因此该方法可以执行任何它想要的操作，包括 return nil、 return10或格式化您的硬盘。（尽管最后一个不太可能。）

该文件指出：

该块必须返回真或假，并且必须有一个索引 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表示我们正在搜索的元素位于当前元素的右侧。因此，我们要搜索的元素必须在子数组中[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模式所需要的：positive 告诉算法它必须向左看，negative 告诉算法向右看，零表示“你找到了范围”：

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

  • 如果 0 <= k < i，则块返回 ary 的正数，
  • 如果 i <= k < j，则该块为 ary 返回零，并且
  • 如果 j <= k < ary.size，则该块为 ary 返回一个负数。
于 2019-08-29T08:59:13.993 回答
2

尽管有文档，Array#bsearch 但不

从此数组中找到满足给定条件的值

该方法的确切作用是它要求您构造这样的数组ary和这样的块blk，即

查找最小值模式

...代码ary.map(&blk)应该返回一个数组，如

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

然后代码ary.bsearch(&blk)将返回给你最左边的数组元素，它返回truefor bkl.call(element)。

查找任何模式

...代码ary.map(&blk)应该返回一个数组，如

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

然后代码ary.bsearch(&blk)将返回给你first-met-by-bisect-jump数组元素，它返回0for bkl.call(element)。

案例 3-5：

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

没有意义

[10, 20, 50, 80, 110].map{|a| a == 20}
=> [false, true, false, false, false]
  1. [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
  1. [10, 20, 50, 80, 110].bsearch{|a| a <= 50}

也可以使用reverse：

[10, 20, 50, 80, 110].reverse.bsearch{|a| a <= 50}
=> 50
于 2019-08-29T15:11:05.480 回答
2

在您的第三个示例中，您没有满足查找最小值模式的要求之一，即块返回true大于或等于您的搜索值的任何值。

在第三种情况下，您已经切换了值，以便返回true小值和false大值，这再次导致未定义的行为。

同样，在第 5 种情况下，您已经切换了相等检查的顺序。这些方法的要求是，true如果搜索值等于或大于搜索值并且false小于搜索值，则块返回。

通常，如果您可以满足 bsearch 算法的所有要求，即搜索的数组已排序并且您指定了合适的块，则 bsearch 算法非常有效。在这种情况下，它可能比基本find方法更有效。

但是，如果您缺少它的任何要求，您将获得未定义的行为和有效的随机结果。在这种情况下，仅使用Enumerable#findwhich 也适用于数组、哈希、...

于 2019-08-29T08:59:23.497 回答