69-Sqrt(x)

题目

Implement int sqrt(int x).

Compute and return the square root of x.

分析

这个题里面是有许多陷阱的
- 首先确定用二分法处理这个问题
- 然而0-x之间的num的平方有可能会溢出，所以不要使用num*num，如果使用的话要用long long 存储
- 还有left 不能为0，如果mid 也为零的话，x/mid 就会出错误
- 最后一个比较坑的是近似的问题，见注释。

实现

/*
//
Author:fancy
Date : 2017-03-14
Algrithm : 69-Sqrt(x)
Time Complexity: 0(lg(n))
Method: Binary Search

*/
class Solution {
public:
    int mySqrt(int x) {     
        if (x <= 1)
            return x;
        int left = 1;