1.描述

Implement int sqrt(int x).

Compute and return the square root of x.

2.分析

二分法简单题

3.代码

int mySqrt(int x) {
    if (x <= 0) return 0;
    if (x <= 3) return 1;
    
    int low = 2;
    int high = x / 2;
    long long mid = (low + high) / 2;
    for (;;) {
        if (mid * mid == x) return mid;
        if (mid * mid > x) high = mid -1; 
        else if ((mid + 1) * (mid + 1) > x) return mid;
        else low = mid + 1;
        mid = (low + high) / 2;
    }
}