0. 题目

Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:
Input: 4
Output: 2

Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.

1. c++版本

方法1，暴力法，将<x的所有平方计算出来，然后取最接近x的数字

    int mySqrt(int x) {
        double prev, curr, i;
        for (i=0; i<= x; i++){
            curr = i*i;
            if (curr == x)
                return i;
            else if (prev < x && x < curr) {
                return i-1;
            }
            else if (curr < x)
                prev = curr;
        }
        return i;
    }

改进版本： 可以对比x与(x/2)^2，从而大幅缩小遍历的范围

  int mySqrt(int x) {
        double prev, curr, first=0, last=0, i, mid;
        mid = x/2;
        while (mid) {
            curr = mid * mid;
            if (x <= curr) {
                last = int(mid);
            }
            if (x > curr) {
                first = int(mid);
                break;
            }
            mid /= 2;
        }
        for (i = int(first); i <= int(last); ++i) {
            curr = i*i;
            if (curr == x)
                return i;
            if (prev < x && curr > x)
                return i-1;
            if (curr < x)
                prev = curr;
        }
        return i;
    }

优化版本：牛顿法，todo！

2. python版本

 def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        first, last, prev, curr, mid = 0, 0, 0, 0, 0
        mid = x/2
        while mid:
            curr = mid * mid
            if x <= curr:
                last = int(mid)
            if x > curr:
                first = int(mid)
                break
            mid /= 2

        i = first
        while i <= last:
            curr = i * i
            if curr == x:
                return i
            if curr < x:
                prev = curr
            if prev < x and x < curr:
                return i-1
            i = i + 1
        return i