题目leetcode69
二分查找概念
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
示例
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
解题思路
image.png
二分查找伪代码
while (left <= right) {
mid = left + (right - left) / 2;
if (array[mid] == target) {
retrun mid;
} else if (array[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
class Solution {
public static int mySqrt(int x) {
int l = 0, r = x, res = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
// 两个int相乘会溢出，要转为long
if ((long) mid * mid <= x) {
// 返回的是整数部分，小数部分会被舍去
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
}
