二进制搜索中的 [start/2 + mid/2] 和 [(start + mid)/2] 有什么区别?

What is the difference between [start/2 + mid/2] and [(start + mid)/2] in binary search?

提问人:user19117411 提问时间:7/10/2023 最后编辑:Vlad from Moscowuser19117411 更新时间:7/11/2023 访问量:200

问:

在二元搜索算法中,我们将 mid 设置为:

mid = (start + end)/2,与

mid = start/2 + end/2,也等于

mid = 开始 + (结束 - 开始)/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 元素之外,并且 end 更新为 mid - 1 以在数组的左侧进行搜索,如果发现“key”大于 mid 元素,则类似地搜索右侧部分。

当 mid = start/2 + end/2 被使用,mid = (start + end)/2 被使用。 这在计算过程中会受到什么影响?

C++ 函数 binary-search stdarray

评论

1赞 Some programmer dude 7/10/2023
函数的输入是什么?您是否尝试过在监视变量及其值时单步执行调试器中的代码,以查看实际发生的情况?你还记得,二进制搜索工作的绝对要求是你搜索的数据是有的吗?
2赞 nick 7/10/2023
不打算重新计算其中的每一个,但它归结为你的值是整数。整数除法将切断任何小数位。
13赞 Daniel Langr 7/10/2023
(1+3)/2与 不同。1/2+3/2
1赞 500 - Internal Server Error 7/10/2023
mid = start + (end - start)/2与 相同 相同 与 相同。请展示您的价值观。(这一切都假设不会溢出)2*mid = 2*start + (end - start)2*mid = 2*start + end - start2*mid = start + endmid = (start + end)/2start+end
1赞 Pepijn Kramer 7/10/2023
它们在数学上并不等价

答:

4赞 463035818_is_not_an_ai 7/10/2023 #1

您需要考虑整数算术会切断任何小数部分,因此取决于最后一位,您会得到不同的结果。startstop

假设他们是

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

其中 和 是整数,和 是 或 ,则得到MNab10

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 

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

评论

0赞 user19117411 7/10/2023
这意味着,在纸上执行此操作时,所有三个表达式都与 start/2 + end/2 相同,但在编程过程中会影响 intergers 和 float 的解。
1赞 463035818_is_not_an_ai 7/10/2023
@user19117411不,纸上谈兵也是一样的。它的整数算术。你可以在纸上做。它只是不是你习惯的“正常”算术(其中5 / 2 + 5/22 + 2 = 4(5+5)/10(a+b)/2 == a/2 + b/2)
0赞 destructioneer 7/16/2023
它不是用实数甚至自然数的数学,用你的任何变量代替,,。所以普通的数学是行不通的。你是 ,所以你正在处理位和字节以及无符号位、寄存器溢出、进位位,而真正处理的是核心的整数数学。x ∉ ℝ ∧ x ∉ ℕxstartendmidxint
2赞 Ofek Shilon 7/10/2023 #2

如上一个答案所述,可以更好地处理残差。 但是,不易溢出。(start + end)/2start/2 + end/2(start + end)/2

因此,如果您要处理具有潜在 >2G 元素的数组,建议使用 // 64b 整数或首选形式。startendmidstart/2 + end/2

6赞 Vlad from Moscow 7/10/2023 #3

对于初学者来说,该功能是无效的。当等于然后你有由于这个语句size1

int start = 0, end = size - 1;

等于 .end0

在本例中,while 循环

while(start < end){

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

int last = -1;

// ...

return last;

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

至于你的问题,那么当 和 都是奇数值时,表达式的值将少一个startendmid

start/2 + end/2

然后对于其他两个表达式。

至于这个表达式,那么它是不安全的,因为 总和可能溢出 .(start + end)/2start + end

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

至于整个函数,那么在标头中已经声明了标准算法,可以适应使用而不是函数。std::upper_bound<algorithm>

3赞 user1095108 7/10/2023 #4

所有这些都是为了在计算中点时防止溢出:

(a + b) / 2

最好的方法(据说)是这样的:

a + b = (a ^ b) + (a & b) << 1
(a + b) / 2 = (a ^ b) / 2 + (a & b)

这个身份来自Don Knuth的著作《计算机编程的艺术》(The Art of Computer Programming, Vol. 4)。

这是因为唐的公式据说是防弹的。它应该在负指数和正指数上同样有效。请注意,向右移动(包括算术)并不总是与除以 2 相同。

评论

0赞 CookedCthulhu 7/27/2023
如果代码使用有符号整数作为数组索引,则转换为无符号 int 也有效: 。(a + b) / 2 = (int)(((uint)a + (uint)b) >> 2)
0赞 user1095108 7/28/2023
@CookedCthulhu AFAIK,((uint)a + (uint)b) 可以溢出,为什么要移动 2 位?错别字,你不明白这一点。
0赞 CookedCthulhu 7/28/2023
这种转变是一个错别字,但公式不能溢出,因为正有符号 int 最多是 ,如果你先将 a 和 b 都转换为无符号,这是有效的。无符号移位不做符号扩展,所以最多是.这个公式在 C# 的源代码中被多次使用,因此它有可能比所谓的最佳方式更快或至少更具可读性。a + b2^32 - 2((uint)a + (uint)b) >> 12^31 - 1
0赞 user1095108 7/28/2023
@CookedCthulhu不正确,则无符号整数中没有符号位。
0赞 CookedCthulhu 7/28/2023
“无符号移位不做符号扩展(因为无符号整数中没有符号位)”。更好?这是我写的。