Sqrt(x)

    Implement .

    题解 - 二分搜索

    由于只需要求整数部分，故对于任意正整数 x, 设其整数部分为 k, 显然有 1 \leq k \leq x, 求解 k 的值也就转化为了在有序数组中查找满足某种约束条件的元素，显然二分搜索是解决此类问题的良方。

    Python

    Java

    1. 异常检测，先处理小于等于0的值。
    2. 使用二分搜索的经典模板，注意不能使用lb < ub, 否则在给定值1时产生死循环。
    3. 最后返回平方根的整数部分lb.
    4. C++ 代码 mid 需要定义为long long，否则计算平方时会溢出，定义 mid 放在循环体外部有助于提升效率。

    复杂度分析

    经典的二分搜索，时间复杂度为 O(\log n), 使用了lb, ub, 变量，空间复杂度为 O(1).