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;
    }
}

邮件订阅,随时获取更新信息

发表评论

电子邮件地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.