二进制搜索Ruby

Question

我想写一个简单的代码来模拟二进制搜索，让我们假设数组已经排序了。x是数组，y是我要找的数。我想知道需要多少步才能找到y(计数器是我想要的结果)。我的代码有什么问题?

非常感谢!

x = ["2,", "5", "7", "10", "20", "30", "50", "90", "101", "120"]
y = 101
mid = (x.count.to_f/2).ceil
z = x[mid].to_i
counter = 0
while y != z
  counter += 1
  if y < z
    mid = (mid/2).ceil
  else
    mid = mid + (mid/2).ceil
  end
end
print(counter)

Answer 1

这不起作用，因为您的数组包含string。字符串按字母顺序比较。

"5" > "10"
=> true

因此，您的数组没有排序。但是，您可以添加前导零，以便字符串比较像您期望的那样工作:

a.map{|e| e.rjust(4, "0") }
"0005" < "0010"
=>true

Answer 2

感谢大家的投入，我使它工作:

x = [2, 5, 7, 10, 20, 30, 50, 90, 101, 120]
puts "Which character you want to find?"
y = gets.chomp.to_i
first = 0
last = x.count - 1
mid = (x[first..last].count.to_f/2).ceil
z = x[mid-1].to_i
counter = 1
while y != z
  counter += 1
  if y < z
    last = mid
    mid = mid - (x[first..last].count/2).ceil
    z = x[mid]
  else
    first = mid
    mid = mid + (x[first..last].count.to_f/2).ceil
    z = x[mid-1]
  end
end
puts "the answer is #{counter}."