algorithm - 为什么二进制搜索 while 循环条件(l+1!= u)？

Question

a = (1..10).to_a
def search(x, t)
  l = -1
  u = x.length

  while l+1 != u
    m = (l + u) / 2.round
    if x[m] < t
      l = m
    else
      u = m
    end
    puts "l:\t#{l} u:\t #{u} m:\t#{m}"
  end

  p = u
  puts "p: #{p} -> #{x[p]}"
  if p >= x.length || x[p] != t
    p = -1
  end
end

search(a, 5)

我研究了很久，但找不到原因，

1. l = -1

   why initial assign the l to -1

2. while循环条件为什么是l+1 != u比l < u

想明白那个方法，终于吃不下了

可以帮助我吗？ 😃

Answer 1

l 和 u 是二分查找的低位和高位。

在这里，您将 l 分配给 -1，将 u 分配给 x.length。您可以轻松地将 l 的赋值从 -1 更改为 0，并将条件 l+1 != u 更改为 l < u。