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] 可以 return 正确地索引号码。为什么 ary[i] - 1 不起作用？

Answer 1

Array#bsearch returns 数组的一个元素，不是匹配元素的索引。

您可能想改用 Array#index。

Answer 2

Array#bsearch 用于执行二进制搜索以查找满足特定条件的元素。根据 documentation，如果您从块中 return 数值，则使用 find-any mode 类型的搜索。

搜索从排序数组的中心开始 - 如果块 return 的值为负值，则继续搜索上半部分，如果块 return 的值为正值，则继续搜索在数组的后半部分。

在您使用 ary[i] - 1 的情况下，由块编辑的值 return 始终为正，搜索继续递归地对数组的后半部分进行搜索 - 永远找不到值 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 3

如果要查找元素的索引而不是元素本身，则需要使用Array#bsearch_index。注意：此方法在 Ruby 2.3 中引入，在撰写本文时尚未发布（将于 2015 年圣诞节发布）。

feature request for Array#bsearch_index contains a comment by Yusuke Endoh showing how to implement Array#bsearch_index (and in fact Array#bsearch as well) based on 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，因为它们是相同的）。该块需要 return 正数表示您正在搜索的索引左侧，负数表示您正在搜索的索引右侧，0 表示您正在搜索的范围内的索引。你的街区恰恰相反。

reversed expression in bsearch block not working