题解 | #NC32 求平方根#

import java.util.*;

import java.util.*;

public class Solution {
    public int sqrt (int x) {
        // 预处理
        if (x == 0) return 0;
        if (x == 1) return 1;
        
        // 初始化
        int left = 1;  // 左边界
        int right = x; // 右边界

        // 二分查找
        int mid = -1;
        while (true) {
            // 获取中间位置
            mid = left + (right -left )/2;
            // 判断是否命中
            if (mid <= x/mid && x/(mid+1) < (mid+1)) {
                return mid;
            } 
            // 未命中则调整区间值
            if (mid > x/mid) { // mid过大
                right = mid -1;
            } else { // mid过小
                left = mid + 1;
            }
        }
    }
}