代码之家  ›  专栏  ›  技术社区  ›  Matt

二进制搜索比较

  •  4
  • Matt  · 技术社区  · 8 年前

    我有一些执行二进制搜索的代码。为什么必须与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;
      }
    
    2 回复  |  直到 8 年前
        1
  •  3
  •   Joe C    8 年前

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

    L == U == 0 . 即使这一个元素恰好是您要查找的元素,因为 while 条件不满足 < ,找不到您的元素。

        2
  •  2
  •   Dave Cousineau    8 年前

    L 和 U 名字可能更好 L R

    这不仅适用于一个元素列表。例如,搜索列表 { 1, 2, 3 } 对于元素 1 . 你会检查的 2 ,看到它更大,减少 U 到0,然后需要检查元素 0 ,只有当您继续检查 L == U .