c++ - 二分法的一个困惑

问题描述

// Forward declaration of guess API.// @param num, your guess// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0int guess(int num);class Solution {public: int guessNumber(int n) {int l = 1, r = n; while (l < r){ int m = l + (r - l) / 2; int res = guess(m); //cout << res << endl; if (res == 0){return m; } else if (res == 1){l = m + 1; } else if (res == -1){r = m - 1; }}return l; }};

这是leetcode上的一道二分题目，请问一下 int m = l + (r - l) / 2;与 int m = (l + r) >> 1区别在哪里哦？为什么我用后者直接超时了，前者过了。为什么前者更快啊，后者不是位运算吗

问题解答

overflow

(l + r) 有可能溢出，可以用

l + (r - l) >> 1;回答3：

我来补充下楼上2位说的，r如果为INT_MAX，那INT_MAX+1就溢出了