LeetCode - Sqrt(x) 代码分析

LeetCode -- Sqrt(x) 代码分析

不少人跟我提过LeetCode 但是知道今天才尝试着在上面交了一个题,连交三遍,终于过了,激动ing....

链接地址:http://oj.leetcode.com/problems/sqrtx/

实现代码:

#include <iostream>
#include <fstream>
using namespace std;
class Solution
{
public:
    int sqrt(int x)
    {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (x < 0)
            return -1;
        if (x == 0 || x == 1)
            return x;

        long long int start = 1;//不能用int 至于为啥,请看下面这位大神的解释
        long long int end = x;
        long long mid;
        /*
            You should use "long long".
            Sometimes, "long" == "long int" == "int" or "short"
            == "short int" == "int". It depends on the system.
        */
        while (start <= end)
        {
            mid = start + (end - start)/2;
            if (mid * mid <= x && (mid+1)*(mid+1) > x)
                return mid;
            else if (mid * mid < x)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return 0;
    }
};
// 测试代码
int main()
{
    freopen("input.txt","r",stdin);
    int test;
    Solution s;
    while (cin >> test)
    {
        cout << s.sqrt(test) << endl;
    }
    return 0;
}
//测试数据:
//-2 -1 0 1 2 3 4 5 6 7 8 9 10 -2147483647 2147483647