x的平方根

描述

实现 int sqrt(int x) 函数,计算并返回 x 的平方根。

样例
  • sqrt(3) = 1
  • sqrt(4) = 2
  • sqrt(5) = 2
  • sqrt(10) = 3

考察点
  • 寻找中间数
  • 计算值过大,使用long类型
答案
public int sqrt(int x) {
    // write your code here
    int low = 0, high = x;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        long square = (long) mid * (long) mid;
        long square1 = (long) (mid + 1) * (long) (mid + 1);
        long square2 = (long) (mid - 1) * (long) (mid - 1);

        if (square == x) return mid;
        if (square < x && square1 > x) return mid;
        if (square > x && square2 < x) return mid - 1;
        if (square < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}