题解 | #求平方根# 递归二分

发现没有递归方式写的，提供一个。

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if(x==1) return x;
        return sqrtSub(x,1,x/2);
    }
    
    public int sqrtSub(int x, int min, int high){
        if(min>high) return high;
        int mid = min+(high-min+1)/2;
        int s = x/mid;
        if(mid > s){
            return sqrtSub(x,min,mid-1);
        }else if(mid < s){
            return sqrtSub(x,mid+1,high);
        }else{
            return mid;
        }
    }
}