java - 二进制搜索比较

Question

所以我有一些执行二进制搜索的代码。为什么必须将 L 和 U 与 <= 进行比较.我不会得到与 < 相同的结果吗？ ？

  public static int bsearch(int t, List<Integer> A) {
    int L = 0, U = A.size() - 1;
    while (L <= U) { //******cant I just do: while(L<U) *****?
      int M = (L + U) / 2;
      if (A.get(M) < t) {
        L = M + 1;
      } else if (A.get(M) == t) {
        return M;
      } else {
        U = M - 1;
      }
    }
    return -1;
  }

Answer 1

这是一个边缘情况，它不起作用:大小为 1 的列表。

在这种情况下，我们将有 L == U == 0 .即使那个元素恰好是您正在寻找的元素，因为 while条件不满意< ，您的元素永远找不到。