问题描述

Implement int sqrt(int x).
Compute and return the square root of x.

问题分析

1. naive方法：从0到x遍历，找到sqrt(x)；
2. 二分查找：从0到x二分查找，找到sqrt(x)；
3. 改进二分查找：下界从0开始是没跑了，上界却不必是x，x/2+1就够了。

AC代码

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        p = 0
        q = x / 2 + 1
        m = None
        while p <= q:
            m = (p + q)/2
            if m * m == x:
                break
            if m * m > x:
                q = m - 1
            else:
                p = m + 1
        return m if m * m == x else p-1

Runtime: 68 ms, which beats 72.99% of Python submissions.