题解 | #求平方根#

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if (x <= 1){
            return x;
        }
        return sqrt(x, 0, x);
    }

    public static int sqrt(int target,int left, int right){
        int mid = (left + right) / 2;
        long cur = target / mid;
        long curNext = target / (mid + 1);
        if (cur == mid || (cur > mid && curNext < mid + 1)){
            return mid;
        }
        if (cur > mid){
            return sqrt(target, mid, right);
        }
        return sqrt(target, left, mid);
    }
}