ruby - 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？

score 3 · Accepted Answer

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]

score 2 · Accepted Answer

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

您可能想Array#index改用。

score 1 · Accepted Answer

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

功能请求包含Array#bsearch_indexYusuke Endoh 的评论，展示了如何基于以下内容实现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。你的块做相反的事情。

3 回答 3