C++ 刷题坑: 二分查找也没有那么容易写出来

阅读 桌面完整版

最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷 能力立马下降许多)

题意就是 不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是.

很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下:

typedef unsigned long long INT64;

class Solution {
public:
    /**
     * @param num: 一个正整数
     * @return: num 是否是个完全平方数
     */
    bool isPerfectSquare(int num) {
        int low = 1;
        int high = num;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            auto midmid = (INT64)mid * mid;
            if (midmid == num) {
                return true;
            }
            if (num < midmid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
};

用C++来写有几个坑:

• 中间平方 midmid = mid * mid 的值很可能超过了32位整数的范围, 所以需要64位整型.
• mid * mid 表达式结果是32位值, 除非你强制转换成64位.
• (low + high) / 2 取中间的方法也很可能会溢出, 而 low + (high – low) / 2则安全.
• 正确的边界判断while (low <= high) 而不是while (low < high), 很多人在白板上写二分查找很容易犯得错.
• 每次缩小搜索范围的边界都需要 加减一: high = mid – 1 和 low = mid + 1

看似很简单的二分搜索, 却不容易一次性写对.

英文: The C++ Pitfalls of Checking Perfect Square using Binary Search

刷题：程序员的基本技能

刷题是提高编程能力和算法思维的有效方式。

• 延时满足: 带娃刷题第365天
• 竞技编程的边际效应递减
• 力扣刷题打卡2209天竟然断了, 哎
• 娃开始每天都在刷力扣, 他长大以后想当软件工程师
• 力扣 Leetcode 的刷题利器: 在线调试器和自动代码提示完成
• 在LG的OLED智能电视下刷题/力扣
• 面试刷题更像是一种服从性测试
• 力扣刷题2000天
• 力扣刷题获得一件衣服奖励(Leetcode DCC Winner)
• 和媳妇约会影响我刷题的速度
• 第一次在动车上刷题: 国内的火车又快又舒服又便宜
• C++ 刷题坑: 二分查找也没有那么容易写出来
• 周末刷刷题找回ACM-er 的感觉
• 找一个 IPAD 9.7能刷题的蓝牙键盘不容易
• 程序员能刷题的网站和资源(我的刷题经验之谈)
• 时间碎片用来刷题是再好不过的了
• 熟能生巧 - 刷题的一些技巧的经验之谈
• 体验 Google Kickstart 刷题

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版