69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

思路：

这道题不难，用binary search 1-x就行，有几个需要注意的细节

1. 求中间值用start+ (end-start)/2，别用(start+end) /2，原因避免start+end求和超出范围
2. mid*mid == x也别用，用 mid = x/mid，理由和上面一致。

public class Solution {
    public int mySqrt(int x) {
        int start=1;
        int end = x;
        if(x<2) return x;
        while(start<end){
            int mid = start+ (end-start)/2;
            if(mid <= x / mid && (mid + 1) > x / (mid + 1)){
                return mid;
            }
            if(mid > x / mid){
                end =mid;
            }
            else{
                start =mid+1;
            }
        }
        return -1;
    }
}