题解 | 求平方根

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param x int整型 
     * @return int整型
     */
    public int mysqrt (int x) {
        // x^2 >= 4x在 x >= 4时明显成立
        return binarySearch(x/2,x);        
    }
    public int binarySearch(int arri, int t) {
        // arr 从 1到 arri
        int l = 1, r = arri;
        int closest = -1;
        boolean found = false;

        if (t == 0) return 0;
        else if (t < 4) return 1;

        while (l <= r) {
            int mid = l + ((r - l) >> 1);//向下取整
            if ((long) mid * mid == t) {
                found = true;
                closest = mid;
                r = mid - 1;
            } else if ((long) mid * mid < t) {
                if(!found)
                    closest = mid;// 没找到才记录
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        // 如果找到x，返回左边界；否则返回比目标值小的最近的更小值，如果没有则返回-1
        return closest;
    }
}