分析

以二分查找最后一次 left = n - 1，right = n 举例进行分析。

第一种情况：

1
2
3
4
5
while (left < right) {
    int mid = left + (right - left >> 1);
    if (check(mid)) left = mid + 1;
    else right = mid;
}

此时 mid = n - 1，如果 check(mid) = true，那么 left = mid + 1 = n，可以正常结束循环；如果 check(mid) = false，那么 right = mid = n - 1，同样可以正常结束循环。

这个时候的查找结果偏向于 right，以 升序区间 来说，相当于 大于等于 的情况。

第二种情况：

1
2
3
4
5
while (left < right) {
    int mid = left + (right - left >> 1);
    if (check(mid)) left = mid;
    else right = mid - 1;
}

此时 mid = n - 1，如果 check(mid) = true，那么 left = mid = n - 1，进入死循环；如果 check(mid) = false，那么 right = mid - 1 = n - 2，right < left 虽然可以正常结束循环，但是没有准确的结果（因为不知道结果是 left 还是 right）。

第三种情况：

1
2
3
4
5
while (left < right) {
    int mid = left + (right - left + 1 >> 1);
    if (check(mid)) left = mid + 1;
    else right = mid;
}

此时 mid = n，如果 check(mid) = true，那么 left = mid + 1 = n + 1，虽然可以正常结束循环，但是没有准确的结果（因为不知道结果是 left 还是 right）；如果 check(mid) = false，那么 right = mid = n，进入死循环。

第四中情况：

1
2
3
4
5
while (left < right) {
    int mid = left + (right - left + 1 >> 1);
    if (check(mid)) left = mid;
    else right = mid - 1;
}

此时 mid = n，如果 check(mid) = true，那么 left = mid = n，可以正常结束循环；如果 check(mid) = false，那么 right = mid = n - 1，同样可以正常结束循环。

这个时候的查找结果偏向于 left，以 升序区间 来说，相当于 小于等于 的情况。

结论

  • int mid = left + (right - left >> 1) 配合着 left = mid + 1 使用；int mid = left + (right - left + 1 >> 1) 配合着 right = mid - 1 使用。需要注意的是 >> 的运算优先级要低于 +-。

  • 使用 left = mid + 1，查找结果偏向于 right，以 升序区间 来说，相当于 大于等于 的情况；使用 right = mid - 1，查找结果偏向于 left，以 升序区间 来说，相当于 小于等于 的情况。

算法模板

第一种

查找结果偏向于 right，以 升序区间 来说，相当于 大于等于 的情况。

1
2
3
4
5
6
7
8
9
10
int left = 0;
int right = 1000000;
while (left < right) {
    int mid = left + (right - left >> 1);
    if (check(mid)) {
        left = mid + 1;
    } else {
        right = mid;
    }
}

第二种

查找结果偏向于 left，以 升序区间 来说，相当于 小于等于 的情况。

1
2
3
4
5
6
7
8
9
10
int left = 0;
int right = 1000000;
while (left < right) {
    int mid = left + (right - left + 1 >> 1);
    if (check(mid)) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

__END__