提问人:user19117411 提问时间:7/10/2023 最后编辑:Vlad from Moscowuser19117411 更新时间:7/11/2023 访问量:200
二进制搜索中的 [start/2 + mid/2] 和 [(start + mid)/2] 有什么区别?
What is the difference between [start/2 + mid/2] and [(start + mid)/2] in binary search?
问:
在二元搜索算法中,我们将 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 被使用。 这在计算过程中会受到什么影响?
答:
您需要考虑整数算术会切断任何小数部分,因此取决于最后一位,您会得到不同的结果。start
stop
假设他们是
start = M*2 + a;
end = N*2 + b;
其中 和 是整数,和 是 或 ,则得到M
N
a
b
1
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
只有第二个表达式不依赖于是否或为偶数或奇数。我实际上并没有费心去计算(通过 2x2 表)是否产生与 .然而,在处理整数算术时,你最好不要依赖直觉,因为太容易被一个(或多个)所偏离。此外,我还没有考虑整数溢出。当溢出时,则不会。start
end
a + (b-a)/2
(a+b)/2
start+end
(start/2) + (end/2)
评论
5 / 2 + 5/2
2 + 2 = 4
(5+5)/10
(a+b)/2 == a/2 + b/2
)
x ∉ ℝ ∧ x ∉ ℕ
x
start
end
mid
x
int
如上一个答案所述,可以更好地处理残差。
但是,不易溢出。(start + end)/2
start/2 + end/2
(start + end)/2
因此,如果您要处理具有潜在 >2G 元素的数组,建议使用 // 64b 整数或首选形式。start
end
mid
start/2 + end/2
对于初学者来说,该功能是无效的。当等于然后你有由于这个语句size
1
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
start + end
请注意,在 C++20 中,标头中声明了可以而且应该使用的函数,而不是手动编写的表达式。std::midpoint
<numeric>
至于整个函数,那么在标头中已经声明了标准算法,可以适应使用而不是函数。std::upper_bound
<algorithm>
所有这些都是为了在计算中点时防止溢出:
(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 相同。
评论
(a + b) / 2 = (int)(((uint)a + (uint)b) >> 2)
a + b
2^32 - 2
((uint)a + (uint)b) >> 1
2^31 - 1
评论
(1+3)/2
与 不同。1/2+3/2
mid = start + (end - start)/2
与 相同 相同 与 相同。请展示您的价值观。(这一切都假设不会溢出)2*mid = 2*start + (end - start)
2*mid = 2*start + end - start
2*mid = start + end
mid = (start + end)/2
start+end