您好我正在查看问题的C解决方案“假设一个排序的数组在事先未知的某个枢轴处旋转.(即,0 1 2 4 5 6 7可能变为4 5 6 7 0 1 2).你好.有效地在旋转的数组中找到一个元素？你可以假设数组中没有重复.“
int rotated_binary_search(int A[],int N,int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
// Avoid overflow,same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;
// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
并看到评论说使用M = L((R – L)/ 2)而不是M =(L R)/ 2避免溢出.这是为什么？先生
解决方法
因为它确实……
让我们假设你使用无符号字符一分钟(当然也适用于更大的整数).
如果L为100且R为200,则第一个版本为：
M = (100 + 200) / 2 = 300 / 2 = 22
100 200个溢出(因为最大的无符号字符是255),并且得到100 200 = 44(无符号否.).
第二,另一方面：
M = 100 + (200-100) / 2 = 100 + 100 / 2 = 150
没有溢出.
正如@ user2357112在评论中指出的那样,没有免费的午餐.如果L为负数,则第一个版本可能不起作用.
