x 的平方根
力扣鏈接：x 的平方根
題目
給你一個(gè)非負(fù)整數(shù) x 偏序，計(jì)算并返回 x 的 算術(shù)平方根 。
由于返回類型是整數(shù)晃虫，結(jié)果只保留 整數(shù)部分 余耽，小數(shù)部分將被 舍去 。
注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符晨仑，例如 pow(x, 0.5) 或者 x ** 0.5 意乓。
示例 1：
輸入：x = 4
輸出：2
示例 2：
輸入：x = 8
輸出：2
解釋：8 的算術(shù)平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去惜傲。
提示：
0 <= x <= 231 - 1
分析
從題目的要求和示例我們可以看出洽故，這其實(shí)是一個(gè)查找非負(fù)整數(shù)的問題，并且這個(gè)整數(shù)是有范圍的盗誊。
如果這個(gè)整數(shù)的平方等于輸入整數(shù)时甚，那么這個(gè)整數(shù)就是結(jié)果隘弊。
如果這個(gè)整數(shù)的平方大于輸入整數(shù)，那么這個(gè)整數(shù)肯定不是結(jié)果撞秋。
如果這個(gè)整數(shù)的平方小于輸入整數(shù)长捧，那么這個(gè)整數(shù)可能是結(jié)果。
因此我們可以使用「二分查找」來查找這個(gè)整數(shù)吻贿，不斷縮小范圍去找
猜的數(shù)平方以后大了就往小了猜串结；
猜的數(shù)平方以后恰恰好等于輸入的數(shù)就找到了；
猜的數(shù)平方以后小了舅列，可能猜的數(shù)就是肌割，也可能不是。
public class Solution {
public int mySqrt(int x) {
// 特殊值判斷
if (x <= 1) {
return x;
}
int left = 1;
int right = x / 2;
// 在區(qū)間 [left..right] 查找目標(biāo)元素
while (left < right) {
int mid = left + (right - left + 1) / 2;
// 注意：這里為了避免乘法溢出帐要，改用除法
if (mid > x / mid) {
// 下一輪搜索區(qū)間是 [left..mid - 1]
right = mid - 1;
} else {
// 下一輪搜索區(qū)間是 [mid..right]
left = mid;
}
}
return left;
}
}
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
int ans = -1;
while(left <= right){
int mid = (left + right) /2 ;
if((long)mid*mid > x){
right = mid - 1;
}else if (mid * mid <= x) {
// ans = mid;
left = mid + 1;
}
}
return ans;
}
}
不管生活多么苦難把敞，我們都要堅(jiān)持下去。因?yàn)榍胺降穆愤€很長(zhǎng)榨惠，未來的日子更加美好奋早。每一次的挑戰(zhàn)都是成長(zhǎng)的機(jī)會(huì)，每一次的努力都會(huì)有回報(bào)赠橙。相信自己耽装，相信未來，讓我們一起走向幸福的明天期揪！
