题目

Implement int sqrt(int x).

Compute and return the square root of x.

分析

计算x的算术平方根。用二分依次对比大小，最后即可找到其算术平方根，不过要注意输入参数为int，因此我选用了0-100000范围，使用二分法依次平方与x比较，注意平方后会超过int的范围，因此需要使用long long类型。

int mySqrt(int x) {
    long long p=0,q=100000;
    while(p<q)
    {
        long long temp=(p+q)/2;
        if(temp*temp==x)
        {
            return temp;
        }
        else if(temp*temp<x)
        {
            p=temp+1;
        }
        else
        {
            q=temp-1;
        }
    }
    while(p*p>x)
    {
        p--;
    }
    return p;
}