17-x的平方根--二分法

题目链接

区间寻找某一个数字使用二分法

class Solution {
    // 1.我的暴力算法，54ms,5.03%
    public int mySqrt1(int x) {
        for(int i = 1; i < x; i++) {
            if(i > x/i) {
                return i-1;
            }
        }
        return x==0?0:1;
    }
    // 2.我的二分查找,1ms，94.76%
    public int mySqrt2(int x) {
        if(x == 0) return 0;
        int left = 1, right = x;
        while(left < right) {
            int mid = (right - left)/2 + left;
            // System.out.println(mid);
            if(mid <= x/mid && (mid+1) > x/(mid+1)) {
                return mid;
            } else if(mid < x/mid){
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return left;
    }
    // 3.老师的二分查找,1ms,94.76%
    public int mySqrt(int x) { 
        if(x == 0) return 0;
        int index = -1, left = 1, right = x;
        while(left <= right) {
            int mid = (right - left)/2 + left;
            if(mid <= x/mid) {
                index = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }
}