力扣精选算法100道——x的平方根(二分查找专题)

x的平方根


?

首先看到这个题目的时候，我们需要对上一个二分查找专题的题目进行深度理解，然后了解模板，这题是完全利用的上一题的模板知识进行，如果直接看这个题目可能是有点懵的，因为我这里直接利用模板进行解题。力扣精选算法100题——在排序数组中查找元素的第一个和最后一个位置(二分查找专题)-CSDN博客

点击这个链接，即可进入。

第一步：题目解析

题目很简单其实，我们只需要找到一个数的平方根即可，8的平方根是2.8....，我们只需要返回正数即可，小数去掉。

第二步：算法原理

首先我们暴力分析：

暴力解法

我们从1开始进行平方，如果平方的结果小于x那么我们继续，如果大于x我们就返回上一个值即可，如果等于x我们就返回那个值即可。

暴力解法
class Solution {
public:
    int mySqrt(int x) {
        int j=INT_MAX;
        for(long long i=1;i<j;i++)
        {
            if(i*i==x)
            {
                return i;
            }
            if(i*i>x)
            {
                return i-1;
            }
        }
        return -1;
    }
};

我们首先看看是否有“二分段”这样才能确定是否能用二分查找算法。

?二分查找

这时候我们可以用到模板了，一部分是x<=t，一部分是x>t部分，我们可以使用区间的右端点模板。

第三步：代码实现

//二分查找
class Solution{
public:
     int mySqrt(int x)
     {
         if(x<1)return 0;//处理边界情况
         int left=1,right=x;
         while(left<right)
         {
             long long  mid=(right-left+1)/2+left;//防止溢出
            if(mid*mid<=x)left=mid;
            else right=mid-1;
         }
         return left;
     }
};