x的平方根（easy）
更好的閱讀體驗應該是：
- 審題-思考
- 答題
- 整理-歸納
一、題目
LeetCode：69.x 的平方根
計算并回傳 x 的平方根，其中 x 是非負整數，
由于回傳型別是整數，結果只保留整數的部分，小數部分將被舍去，
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由于回傳型別是整數，小數部分將被舍去，
二、二分法解題
二分查找是一種基于比較目標值和陣列中間元素的教科書式演算法，
- 如果目標值等于中間元素，則找到目標值，
- 如果目標值較小，繼續在左側搜索，
- 如果目標值較大，則繼續在右側搜索，
時間復雜度：O(logN)，
空間復雜度：O(1)，
分析模版
- 我們的目標是找到平方最接近目標數字的值
- 相對于基礎模版，我們要知道的數字是逼近目標值的，即
mid * mid <= target，大家是否感覺這道題和上一題幾乎一模一樣～
Javasciprt 代碼
var mySqrt = function(x) {
// 確定條件，k方 <= x
let min = 1; // 左邊界
let max = x; // 右邊界
let temp = 0; // 存盤結果值，因為它會逐漸逼近最終結果
while (min <= max) {
let mid = min + ((max - min) >> 1);
if (mid * mid <= x) {
// 這里mid * mid = x 時，我仍然移動了左邊界，并且跳過的mid，不要怕
// 它被保存在了temp中，知道回傳它或被新的元素覆寫
temp = mid;
min = mid + 1; // 忽略左測區間
} else {
max = mid - 1; // 忽略右側區間
}
}
return temp;
};
三、寫在最后
本文是二分查找-模版 I 的第三題，僅僅是修改與目標值之間的關系，我們一鼓作氣拿下下一道題吧！
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵~
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- JavaScript 版 LeetCode 題解
- 前端進階筆記
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/232476.html
標籤：其他
下一篇：Vue路由