每天一道算法题【蓝桥杯】【x的平方根】
思路
使用二分查找模型来避免超时
条件为
mid * mid <= x
mid*mid>x
注意使用longlong类型
#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
int mySqrt(int x) {
long long left = 0, right = x;//定义成longlong类型防止内存溢出
long long mid = 0;
while (left < right)
{
mid = left + (right - left + 1) / 2; //朴素的二分查找模型
if (mid * mid <= x) left = mid; //二分查找的两段性
else right = mid - 1;
}
return left;
}
}