二分查找比较

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;
  }

- Matt

---

那么一个大小为1的列表怎么办？ - Joe C

这取决于L和U的初始定义。 - Alfabravo

考虑L == U的情况，如果使用<=，你将检查该元素，而<则不会。 - marcadian

但是如果A.get(M) == t，我们就返回M。因此L == U不应该是一个问题。 - Matt

Answer 1

这里有一个边缘情况，这种方法可能不起作用：列表大小为1。

在这种情况下，我们会得到L == U == 0。即使那个元素恰好是你要查找的元素，由于while条件不满足小于号，你的元素也永远找不到。

- Joe C

---

那会是唯一的边缘情况吗？ - Matt

我能想到的只有这一个。虽然我不能保证这是唯一存在的边缘情况。 - Joe C

@Matt 许多其他情况，例如数字0-99的列表搜索1，我会让你和乔想出原因。 - Oleg

@Oleg 不好意思，Joe快要去睡觉了 :) - Joe C

Answer 2

L和U可能更好地命名为L和R。它们定义了数组未搜索部分的左侧和右侧范围。如果您的搜索缩小到单个元素，则它们将相等，但是为了测试最后一个元素，while条件必须成立，否则您将跳过它。

这不仅适用于一个元素的列表。例如，在列表{ 1, 2, 3 }中搜索元素1。您将检查2，看到它大于目标元素，将U减少到0，然后需要检查元素0，这只有在L == U时继续检查才能发生。

- Dave Cousineau