Leetcode JAVA刷刷站（69）x的平方根

一、题目概述

二、思路方向

在Java中，计算一个非负整数x的算术平方根，并返回其整数部分，你可以使用二分查找法。这是因为平方根函数是单调递增的，所以我们可以利用二分查找在合理的时间复杂度内找到结果。

三、代码实现

public class Solution {  public int mySqrt(int x) {  if (x == 0) {  return 0;  }  long left = 1, right = x; // 使用long类型避免平方时溢出  while (left <= right) {  long mid = left + (right - left) / 2; // 防止溢出  long square = mid * mid;  if (square == x) {  return (int) mid;  } else if (square < x) {  left = mid + 1;  } else {  right = mid - 1;  }  }  // 当left > right时，循环结束，right为最接近x的平方根的整数（向下取整）  return (int) right;  }  public static void main(String[] args) {  Solution solution = new Solution();  int x = 9;  System.out.println("The square root of " + x + " is " + solution.mySqrt(x));  x = 8;  System.out.println("The square root of " + x + " is " + solution.mySqrt(x));  }  
}

执行结果：

四、小结

在这个例子中，我们使用了long类型来存储left、right和mid的值，以防止在计算mid * mid时可能出现的整数溢出。注意，在计算平方后，我们立即将其与x进行比较，以决定下一步的搜索范围。

循环会持续进行，直到left大于right。此时，right变量将包含最接近x的平方根的整数（向下取整）。这是因为我们在square > x时将right设置为mid - 1，从而确保我们不会错过任何可能的解，并且最终将right定位到最接近但不大于x的平方根的整数。

最后，我们将right的值转换为int类型并返回，因为题目要求返回的是整数部分。