Merge pull request halfrost#146 from hanlins/69/sqrtx/consise-binary-search

halfrost · web-flow · commit d0c6f905f67b · 2021-06-05T23:40:24.000+08:00
Make the binary search solution more concise for Sqrt x
diff --git a/leetcode/0069.Sqrtx/69. Sqrt(x).go b/leetcode/0069.Sqrtx/69. Sqrt(x).go
@@ -1,23 +1,18 @@
 package leetcode
 
-// 解法一 二分
+// 解法一 二分, 找到最后一个满足 n^2 <= x 的整数n
 func mySqrt(x int) int {
-	if x == 0 {
-		return 0
-	}
-	left, right, res := 1, x, 0
-	for left <= right {
-		mid := left + ((right - left) >> 1)
-		if mid < x/mid {
-			left = mid + 1
-			res = mid
-		} else if mid == x/mid {
-			return mid
+	l, r := 0, x
+	for l < r {
+		mid := (l + r + 1) / 2
+		if mid*mid > x {
+			r = mid - 1
 		} else {
-			right = mid - 1
+			l = mid
 		}
 	}
-	return res
+
+	return l
 }
 
 // 解法二 牛顿迭代法 https://en.wikipedia.org/wiki/Integer_square_root
