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);
}
}