69. x的平方根

二分查找

class Solution {
    public int mySqrt(int x) {

        int left = 0;
        int right = x;

        while (left <= right){

            int mid = left + (right - left) / 2;

            /**
             * 避免整形溢出，转换为long
             */
            if ((long) mid * mid < x){
                left = mid + 1;
            }
            else if ((long) mid * mid > x){
                right = mid - 1;
            }
            else {
                return mid;
            }
        }

        /**
         * 如果目标不存在，返回小于目标的前一个元素
         */
        return right;
    }
}

/**
 * 时间复杂度 O(logn)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/sqrtx/