69. x 的平方根

Leetcode题目:二分查找

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 231 - 1

解题思路

二分查找

好久没写二分查找的题了,这次又跪了,令人感慨。过几天等忘的差不多了再用go写一遍,这几天先重新复习下二分查找。

C++
class Solution {
public:
    int mySqrt(int x) {
        int left=0,right=x,ans=0;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if((long long)mid*mid<=x)
            {
                ans=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }    
        return ans;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x