1 題目地址
69. x 的平方根 - 力扣（LeetCode）69. x 的平方根 - 給你一個非負整數 x ，計算并返回?x?的 算術平方根 。由于返回類型是整數，結果只保留 整數部分 ，小數部分將被 舍去 。注意：不允許使用任何內置指數函數和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。?示例 1：輸入：x = 4輸出：2示例 2：輸入：x = 8輸出：2解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。?提示： * 0 <= x <= 231 - 1
https://leetcode.cn/problems/sqrtx/description/
2 題目說明
給你一個非負整數?x?，計算并返回?x?的?算術平方根?。
由于返回類型是整數，結果只保留?整數部分?，小數部分將被?舍去 。
注意：不允許使用任何內置指數函數和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。
示例 1：
輸入：x = 4 輸出：2
示例 2：
輸入：x = 8 輸出：2 解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。
提示：
0 <= x <= 231 - 1
3 解題思路
給定target值，計算出算術平方根；其次因為只保留整數部分就可以，所以能可以采用二分法，來找出這個數。
1、直覺上一個整數的平方根肯定不會超過它的一半，但是0和1除外(特殊處理)
2、算數平方根的范圍肯定是在[1,target/2]
3、二分查找法：
????????當middle^2>target，結果在左邊，往左移，right=middle-1；
????????當middle^2<target，結果在右邊，往右移，left=middle+1；
? ? ? ? 當middle^2=target，直接返回
? ? ? ? 當不滿足left<=right，跳出的時候表示right是最接近target的值
4 代碼編寫
4.1?二分查找
class Solution {public int mySqrt(int x) {if (x==0) {return 0;}if (x==1) {return 1;}int left = 1;int right = x / 2;while (left <= right) {int middle = (left + right) / 2;if ((long)middle * middle > x) { // 注意這塊要加上(long)否則可能會因為溢出導致結果異常right = middle - 1; // 左移} else if ((long)middle * middle < x) { // 注意這塊要加上(long)否則可能會因為溢出導致結果異常left = middle + 1; // 右移} else {return middle; // 相等則直接返回}}return right;}
}
)
