Sqrt(x)

题目

Implementint sqrt(int x).

Compute and return the square root ofx.

x is guaranteed to be a non-negative integer.

Example 1:

Input:
 4

Output:
 2

Example 2:

Input:
 8

Output:
 2

Explanation:
 The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

思路分析

这道题刚拿到手感觉没有什么思路，不是那么直接。如果结合binary search，感觉会有一些思路，但也不是直接像其他的binary search题一样去搜索一个target。

这道题的一个难点是如何找到最终的target，一般来讲binary search的target值是left index，或者right index。这道题中的target应该是最终的left index - 1，也就是说target与left index存在着一种mapping

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left, right = 0, x
        while left <= right:
            mid = left + (right-left)/2
            square = mid * mid
            if square == x: return mid
            if square > x: right = mid - 1
            else: 
                left = mid + 1
        return left-1     <<<< the search target is a mapping with left pointer, left-1