模板

left,right=1,n
while left<=right:
    mid=left+(right-left)//2
    if 条件:
        right=mid+1
    else:
        left=mid-1

1. 定义左右边界
2. 左边界小于右边届时进入循环体
3. 取中间数，使用left+(right-left)//2是防止越界的问题
4. 根据业务条件不断的向中间移动left和right

例题

367. 有效的完全平方数

描述

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

示例1

输入：num = 16
输出：true

示例2

输入：num = 14
输出：false

提示

1 <= num <= 2^31 - 1

思路

如果一个数完全平方数，则存在另一个数的平方等于这个数
81=9*9
25=5*5
16=4*4
9=3*3
4=2*2
除了0和1外，一个数的开方结果都要比这个数的一半还要小，所以在遍历时，不用从1到要求的那个数

代码

    def isPerfectSquare(self, num):
        if num<=1:
            return True
        half=num//2
        for i in range(half+1):
            if i*i==num:
                return True
        return False

但是时间复杂度是O(n/2)也挺大的，能不能左右开弓呢，按模板写二分法代码

    def isPerfectSquare(self, num):
        left = 0
        right = num
        while left<=right:
            mid=left+(right-left)//2
            m2=mid*mid
            if m2==num:
                return True
            elif m2>num:
                right=mid-1
            else:
                left=mid+1
        return False

AC: 执行用时：
16 ms
, 在所有 Python 提交中击败了
73.62%
的用户

69.x的平方根

描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例1

输入: 4
输出: 2

示例2

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

提示

见二分法的模板

代码

    def mySqrt(self, x):
        left,right=0,x
        res=0
        while left<=right:
            mid=left+(right-left)//2
            m2=mid*mid
            if m2==x:
                return m2
            elif m2>x:
                right=mid-1
            else:
                left=mid+1
                res=mid#以为是向下取的
        return res

【每日算法】二分查找法

原文：https://www.cnblogs.com/hitechr/p/15100386.html