题目：

Implement int sqrt(int x).

Compute and return the square root of x.

代码：

class Solution {public:        int mySqrt(int x)        {            if (x<2) return x;            int l = 1;            int r = x/2;            while (l<=r)            {                int mid = (l+r)/2;                if ( x / mid < mid )                {                    r = mid - 1;                }                else if ( x / mid > mid )                {                    l = mid + 1;                }                else                {                    return mid;                }            }            return l-1;        }};

tips：

这个题一开始拿到感觉怪怪的，直接看的solution。

比如输入400，记录mid的结果如下：

100

50

25

12

18

21

19

20

这种虽然产生了震荡，但是震荡必然越来越小，而且每次变化的长度至少是上一次的一半，时间复杂度也确实是O(logn).

有个细节，如果没有整数的平方数，最后会推出循环；而退出循环时，一定是从l - r = 1，因此取l-1返回即可。

=====================================================

第一次过的时候有误区，binary search本来就是震荡的过程，第二次过按照第一次的代码写了一遍。

class Solution {public:    int mySqrt(int x) {            if ( x<2 ) return x;            int l = 1;            int r = x/2;            while ( l<=r )            {                int mid = (l+r)/2;                if ( x/mid == mid )                {                    return mid;                }                else if ( x/mid > mid )                {                    l = mid+1;                }                else                {                    r = mid-1;                }            }            return l-1;    }};