题解 | #求平方根#

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if(x < 1) return 0 ;
        if(x < 4) return 1 ;
        int half = x / 2 ;//当x >= 4 时 x^(1/2) 一定 <=  x/2 , 因此直接定位到[0-x/2]
        int i = 0 ;
        int j = half ;
        while(i <= j) {//二分查找
            int mid = i + (j - i) / 2 ;
            if(mid == x / mid) {//将条件【mid * mid == x】 转换为 【mid == x/mid】，避免溢出
                return mid ;
            } else if(mid < x / mid) {
                if((mid + 1) > x / (mid + 1)) {
                    return mid ;
                }
                i = mid + 1;
            } else {
                j = mid - 1 ;
            }
        }
        return j ;
    }
}