二分查找 - 为什么选择 ceil？

Question

我在研究二分查找算法，看到过很多次算法是这样写的（这里是C++，但是语言不是那么重要）：

    int start = 0;
    int end = vec.size() - 1;       
    do {
        int mid = (lo + hi) / 2;
        if (target < vec[mid])
          start = mid + 1;
        else if (target > vec[mid])
          end = mid - 1;
        else
          // found
    } while (start <= end);

不过我也见过这样的实现：

    int start = 0;
    int end = vec.size() - 1;       
    do {
        int mid = (int)ceil((lo + hi) / 2.0);
        if (target < vec[mid])
          start = mid + 1;
        else if (target > vec[mid])
          end = mid - 1;
        else
          // found
    } while (start <= end);

两者似乎都有效。为什么我应该得到 ceil 并执行第二种情况的浮点运算而不是使用第一个版本，是否有任何正确性或性能原因？

Answer 1

当int mid = (lo + hi) / 2:

当 [left, right] 之间的数组大小为奇数时，您通过取两个可能的中间元素的左侧元素来决定 mid 元素，即对于数组 [4, 5]，您的 mid 将是4. 因此，如果没有 floor 的任何 ceil，除法的工作方式与 floor.

非常相似

当(int)ceil((lo + hi) / 2.0);:

当 [left, right] 之间的数组大小为奇数时，您通过取两个可能的中间元素的右侧元素来决定 mid 元素，即对于 [4, 5]，您的 mid 将为 5 .

所以两种选择都有效，因为你是 discarding/taking 基于某些有效条件（target < vec[mid] 和 target > vec[mid]）的一部分，分区点在这里无关紧要.

还有一点就是，在像int mid = (lo + hi) / 2这样的运算中，如果加起来超过了整数范围，那么在加上lo和hi的时候可能会出现溢出。像 mid = lo + (hi - lo) / 2 这样写会产生相同的输出是安全的。

希望对您有所帮助！

编辑

so both work only because I'm discarding the mid element from the new search range when restarting the search, right?

是的。如果您不丢弃 mid 元素，它将陷入无限循环，即 [4, 5]，4 将始终被选为 mid，对于像 left = mid 这样的调用，它会创建一个无限循环。

二分查找 - 为什么选择 ceil？

Binary search - why ceil?

c++

algorithm

binary-search

编辑