c++ - 二分法的一个困惑
怪我咯
怪我咯 2017-04-17 13:59:10
[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 0
int 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区别在哪里哦?为什么我用后者直接超时了,前者过了。为什么前者更快啊,后者不是位运算吗

怪我咯
怪我咯

走同样的路,发现不同的人生

全部回复(3)
阿神

overflow

迷茫

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

l + (r - l) >> 1;
迷茫

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

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号