題目
解題思路
題目要求非負整數 x 的平方根，相當于求函式 y = √x 中 y 的值，
函式 y = √x 影像如下：
從上圖中，可以看出函式是單調遞增的，滿足二分查找的條件（區間是有序的），所以可以用二分查找去做，
解題步驟
- 比較 mid * mid 跟 x 的大小，相等則直接回傳 mid，否則就去以 mid 為分割點的左右區間查找，直到不滿足回圈回圈條件（left == right + 1 或 left == right 究竟是哪一個主要跟回圈條件有關，請看后面的分析）就退出，
- 由于非負整數 x（當 x ≠ 0 時） 的平方根一定是落在區間 [1, x/2 + 1]，所以左右邊界分別取 1 和 x/2 + 1，而不分別取 0 和 x，這樣可縮小查找范圍，
- 為了防止 mid * mid 太大而發生整型溢位，取 mid 跟 x/mid 比較，
說明
右邊界 right 取 x/2 + 1，而不取 x/2，這是因為當 x = 1 時，right 如果取 x/2，由于 x/2 會向下取整使得 x/2 = 0，此時 left = 1 大于 right = 0，以至于直接跳出回圈，導致 1 的平方根為 0，這明顯是錯誤的，
Show me the Code
int mySqrt(int x){
int left = 1, right = x / 2 + 1;
// 回圈不變數 始終維持在區間 [left, right] 中查找，當 left = right + 1 時，區間為空，查找結束
// 當 left == right 時，區間 [left, right] 依然有效
while (left <= right) {
// 防止溢位
int mid = left + ((right - left) >> 1);
// mid 大于 √x ，在 mid 前半區間 [left, mid - 1] 中查找，不是 [left, mid]
// 是因為會當查找到 target 時，直接回傳 mid，所以沒必要再考慮 mid
if (mid > x / mid) {
right = mid - 1;
// mid 小于 √x ，在 mid 后半區間 [mid + 1, right] 中查找
} else if (mid < x / mid) {
left = mid + 1;
// mid 等于 √x ，代表查找到 target，則直接回傳
} else {
return mid;
}
}
return right;
}
補充說明
如果沒有出現 mid == x / mid 的情況，最后到底是 return right 還是 return left？
1、可以通過除錯得出；
2、回圈結束的條件是 left = right + 1，示例中提示了當 x = 8，其平方根是 2，有點類似于向下取整的意思，所以是 return right ，
進一步補充
可能有些童鞋會問到，上面代碼中回圈的條件為何是 left <= right 而不是 left < right，其實這兩個條件都可以，主要區別在于：
回圈結束的條件不一樣，前者是 left = right + 1 后者是 left = right，即前者當 left = right + 1 時，查找區間 [left, right] 為空，后者當 left = right 時，查找區間 [left, right) 為空，
定義的右邊界取值不一樣，前者右邊界取值為 x / 2 + 1，后者可為 x / 2 + 2，
這里會提到一個回圈不變數的概念：
回圈不變數
1. 初始化：它在回圈的第一輪迭代開始之前，應該是正確的，
2. 如果在回圈的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應該保持正確，
3. 當回圈結束時，不變式給了我們一個有用的性質，它有助于表明演算法是正確的，
所以本題回圈的條件可以是 left <= right 也可以是 left < right，關鍵是查找的程序中需要一直維護查找區間 [left, right] 或 [left, right)，
下面補充一個回圈條件為 left < right 的代碼，
最后回傳的是 right - 1，這是因為:
定義的查找區間是左閉右開[left, right)，取不到右邊界 right；當 left == right 時，回圈退出，由于 right 取不到并且平方根有點向下取整的意味，所以取 right - 1；
通過除錯也能得出，
Show me the Code
int mySqrt(int x){
int left = 1, right = x / 2 + 2;
// 回圈不變數 始終維持在區間 [left, right) 中查找，當 left = right 時，區間為空，查找結束
while (left < right) {
// 防止溢位
int mid = left + ((right - left) >> 1);
// mid 大于 √x ，在 mid 前半區間 [left, mid) 中查找
if (mid > x / mid) {
right = mid;
// mid 小于 √x ，在 mid 后半區間 [mid + 1, right) 中查找
} else if (mid < x / mid) {
left = mid + 1;
// mid 等于 √x ，代表查找到 target，則直接回傳
} else {
return mid;
}
}
return right - 1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259648.html
標籤：其他
上一篇：快速地為專案選擇開源許可