x 的平方根

package main.java.simple;

/**

• https://leetcode.cn/problems/sqrtx/description/

• 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

• <p>

• 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

• <p>

• 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
  /
  class Solution {
  public static int mySqrt(int x) {
  //解法：二分查找，找到一个数满足nn<=x&&(n+1)*(n+1)<x
  long left = 1;
  long right = x / 2;
  long mid;
  while (left < right) {
  mid = (left + right + 1) >> 1;
  if ((mid * mid) == x) {
  return (int) mid;
  }
  if ((mid * mid) > x) {
  right = mid - 1;
  }
  if ((mid * mid) < x) {
  left = mid;
  }
  }
  return (int) Math.min(left, x);
  }

  public static void main(String[] args) {
  // System.out.println(mySqrt(4) == 2);
  // System.out.println(mySqrt(8) == 2);
  // System.out.println(mySqrt(10) == 3);
  // System.out.println(mySqrt(1) == 1);
  // System.out.println(mySqrt(0) == 0);
  System.out.println(mySqrt(2147395599) == 46339);
  }
  }