3 数值二分型

• 典型的二分法: 输入是数组，双指针分别是数组的index
• Input不再是Array，不再以index，而是以value来做二分

374. Guess Number Higher or Lower

367. Valid Perfect Square

• ret = mid * mid 来判断范围

class Solution(object):
    def isPerfectSquare(self, num):
        start, end = 1, num
        while start <= end:
            mid = start + (end - start) / 2
            ret = mid * mid
            if ret > num:
                end = mid - 1
            elif ret < num:
                start = mid + 1
            else:
                return True
        return False

69. Sqrt(x)

• 在0～x中找最大的数r，满足r * r < = x
• Why start + 1 < end ?
• 剩余的搜索范围都是满足搜索条件的！

class Solution(object):
    def mySqrt(self, x):
        start, end = 0, x
        while start + 1 < end:
            mid = start + (end - start) / 2
            ret = mid * mid
            if ret > x:
                end = mid - 1
            elif ret < x:
                start = mid
            else:
                return mid

        if end * end <= x:
            return end
        else:
            return start