题解 | #求平方根#

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        //第一思路就是两两乘，二分找
        //但是考虑到向下取整，应该再找一个数来记录最接近的平方值
        if(x<=1){
            return x;
        }
        int left=1;//下标从1开始
        int right=x/2;//提升效率
        int minMid=0;
        
        while(left<=right){
            int mid=left+(right-left)/2;
            if(x/mid>mid){
                left=mid+1;
                minMid=mid;
            }else if(x/mid<mid){
                right=mid-1;
            }else{
                return mid;
            }
        }
        //如果没有返回mid，说明没有完全符合的整数，我们就需要向下取整
        return minMid;
        
    }
}