二分查找中 [start/2 + mid/2] 和 [(start + mid)/2] 有什么区别？

Question

在二分查找算法中，我们将mid设置为：

mid = (start + end)/2 与

mid = start/2 + end/2 并且也等于

中间 = 开始 + (结束 - 开始)/2

但对于相同的算术表达式，这三个都给出不同的结果。这些在计算过程中如何变化？

这是使用二分搜索查找向量数组中元素最后一次出现的代码：

int lastOccurrence(vector<int> arr, int size, int key){
    int start = 0, end = size - 1;
    int last = -1;
    // int mid = start/2 + end/2;
    int mid;
    while(start <= end){
        // mid = start + (end - start)/2;
        mid = (start + end)/2;
        if(key == arr[mid]){
            last = mid;
            start = mid + 1;
        }
        else if(key > arr[mid]){
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
        cout << "start: " << start << "\tend: " << end << "\tmid: " << mid << endl;
    }
    return last;
}

传递给函数的值是：

int main(){
    vector<int> arr = {1,2,3,4,4,4,4,5,6,7,11};
    int size = arr.size();
    int key = 4;
    cout << "First occurrence of " << key << " is at index " << firstOccurrence(arr, size, key) << endl;

    cout << "Last occurrence of " << key << " is at index " << lastOccurrence(arr, size, key) << endl;

    return 0;
}

如果 mid 元素等于所需的“key”元素，则 mid 索引将存储在变量中，并将 start 更新为 mid + 1，以便它可以在数组的右侧部分搜索“key”的任何其他出现。如果发现“key”小于 mid 元素，则意味着该元素不存在于 mid 元素之外，并且末尾更新为 mid - 1 以在数组的左侧部分进行搜索，并且类似地搜索如果发现“key”大于中间元素，则为右侧部分。

当使用 mid = start/2 + end/2 和 mid = (start + end)/2 时，它给出了不同的结果。在计算过程中这是如何受到影响的？

Answer 1

对于初学者来说，该功能是无效的。Whensize等于1then 你有由于这个陈述

int start = 0, end = size - 1;

那end等于0.

在这种情况下，while 循环

while(start < end){

将被跳过。last该函数将返回等于的值-1

int last = -1;

// ...

return last;

虽然arr[0]可以等于key.

至于你的问题，当 和 start都是end奇数时，mid表达式的值将减一

start/2 + end/2

然后是另外两个表达式。

至于这个表达式，(start + end)/2由于 sum 可能溢出，因此它是不安全的start + end。

请注意，在 C++20 中，std::midpoint标头中声明的函数<numeric>可以而且应该用来代替手动编写的表达式。

至于整个函数，那么std::upper_bound标头中已经声明了标准算法<algorithm>，可以适用于代替该函数使用。

Answer 2

您需要考虑整数算术会截断任何小数部分，因此根据最后一位start，stop您会得到不同的结果。

假设他们是

 start = M*2 + a;
 end = N*2 + b;

其中M和N是整数，并且a和b是1or 0，那么你得到

mid_0 = (start + end)/2 = M+N + (a+b) / 2
mid_1 = start/2 + end/2 = M+N
mid = start + (end - start)/2 = M*2 + a + (N-M) + (b-a)/2 = M+N + a + (b-a)/2 

只有第二个表达式不取决于 或start是end偶数还是奇数。我实际上并没有费心去计算（通过 2x2 表）是否a + (b-a)/2产生与(a+b)/2. 然而，在处理整数算术时，你最好不要依赖直觉，因为很容易偏离一（或更多）。而且，我还没有考虑整数溢出。当start+end溢出时则(start/2) + (end/2)不会。