Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis

• 二分法
• 注意不能使用low<high，否则x=1的时候不work
• while跳出时可能情况
  • 1： low+1==end，此时由于sqrt取整，所以一定返回low
  • 2： end==1 || end==2?

Code

public class Solution {
    public int mySqrt(int x) {
        if(x==0) {return 0;}
        int low=1, high=x;
        while(low+1<high){
            int mid = low + (high-low)/2;
            if (mid>x/mid) {high = mid;}
            else {low = mid;}
        }
        return low;
    }
}

Reference

Yuanbin