Ruby 二进制搜索代码未返回预期结果

Question

我正在尝试在 Ruby 中编写二进制搜索方法，发现一个奇怪的情况，在这种情况下，当我将两个数字相加时，我的代码没有 return 我期望的结果并在 elsif 语句中将它们除以二。

当我给该方法一个 1-3 的目标和一个 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 的数组时，该方法就起作用了，我得到了索引我想要的目标。

当我给方法一个目标 4 时，我得到一个无限循环，因为中间 = first + last / 2 代码是 returning 5 而不是预期的 3。我什至尝试打印一个7/2 结果，我得到了 3，但是当它提取值时，它 returns 5.

当我为该方法指定 7-10 的目标时，它中断并表示第 12 行（即 elsif 所在的行）上的 nil:NilClass 有一个未定义的方法“<”。


def binary_search(target, array)
  middle = array.length / 2
  first = 0
  last = array.length - 1

  while first < last
    if array[middle] == target
      puts "we've found the target! middle is #{middle}"
      return true
    elsif array[middle] < target
      first = middle + 1
      middle = first + last / 2
      puts "we're in the elsif and middle is #{middle}"
    else
      last = middle - 1
      middle = first + last / 2
      puts "we're in the else and middle is now #{middle}"
    end
  end
  false
end

binary_search(4, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Answer 1

先决条件：

4 + 4 / 2 会给我们 6。它相当于 4 + (4 / 2 )。
(4 + 4) / 2 会给我们 4.

这两个说法不等价。

关于两个中间计算：

middle = first + last / 2

我们没有达到预期。

您要将 first 和 last 除以二。所以你会想要：

middle = (first + last) / 2

如果您将 first + last / 2 替换为 (first + last) / 2，您的脚本将为我们提供：

binary_search(4, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
we're in the else and middle is now 2
we're in the elsif and middle is 3
we've found the target! middle is 3
 => true

Ruby 二进制搜索代码未返回预期结果

Ruby Binary Search Code is Not Returning Expected Results

ruby

binary-search-tree