二分法，一个看似简单，逻辑易懂的算法，但是初次接触可能会有很多坑！主要是边界处理的问题。

下面以一个耳熟能详的案例来展开：
案例描述：

小B从1~100之间（含边界值）任意想一个数字（目标值），然后给7次机会让小A来猜，如果小A的猜测值大于目标值，则提示“太大了”；如果猜测值小于目标值，则提示“太大了”；如果猜测值等于目标值，则提示“猜对了！”；
在7次内小A猜到了就是小A赢，猜不到就是小B赢。如果你是小A，你会怎么玩这个游戏？

这个就是二分法的经典使用场景，每次都对半猜，7次之内肯定都能猜到结果，因为2^7=128，而提供的猜测范围才100个数，就算在1~128之间来猜也没问题！

一、踩坑之路

根据对半猜的原则，我尝试自己写了一下，跑完发现没什么问题，代码如下：

def binary_serch(array, target):
    l = 0
    r = len(array)-1

    i = 1
    while l <= r:
        m = int(0.5*l+0.5*r)    # 取中间值，索引没有小数，向下取整
        guess = array[m]
        if guess > target:      # 如果猜测值大于目标值，则给右索引赋值猜测值的索引值
            r = m
            print('太大了！')   
        elif guess < target:    # 如果猜测值小于目标值，则给左索引赋值猜测值的索引值
            l = m
            print('太小了！')
        else:                   # 如果猜测值等于目标值，返回结果
            print('猜对了！值为%d，总执行%d次。' % (target, i))
            break
        i += 1                  # 计算循环基础，即猜了几次

if __name__ == '__main__':
    array = [i for i in range(1, 100)]  # 有序数组
    target = random.randint(1,100)
    binary_serch(array, target)

实际上是有问题的，一边的边界值是取不到的，但是由于是随机取数，所以取到两边边界值的概率只有2%，相对较低。可以给target赋值100，查看执行效果，会是一个死循环。因为索引值取到98和99时，int((98+99)/2)永远是98，取不到索引值99。

如果进行四舍五入取值呢？会进入另外一个端点的边界值取不到，即当索引值取到0和1时，(0+1)/2永远是1，取不到索引值0。

这种某一端点取不到边界值的情况，只能通过加一个判断逻辑进行处理（如下代码），但是这样的处理方式似乎不是明智之举，二者的判断有些脱离了，在变种时，比如说查找第一个或者最后一个大于或小于某值的值，便会有一些吃力，很难用原有的逻辑进行扩展。

def binary_serch(array, target):
    l = 0
    r = len(array)-1

    i = 1
    if target == array[r]:
        print('猜对了！值为%d，总执行%d次。' % (target, i))
        return 0
    while l <= r:
        m = int(0.5*l+0.5*r)    # 取中间值，索引没有小数，向下取整
        guess = array[m]
        if guess > target:      # 如果猜测值大于目标值，则给右索引赋值猜测值的索引值
            r = m
            print('太大了！')
        elif guess < target:    # 如果猜测值小于目标值，则给左索引赋值猜测值的索引值
            l = m
            print('太小了！')
        else:                   # 如果猜测值等于目标值，返回结果
            print('猜对了！值为%d，总执行%d次。' % (target, i))
            break
        i += 1                  # 计算循环基础，即猜了几次

if __name__ == '__main__':
    array = [i for i in range(1, 101)]  # 有序数组
    # target = random.randint(1,100)
    target = 100
    binary_serch(array, target)

二、解决方案

后来，在网上看到了一个很妙的处理方式，就是将开始的索引值和结束的索引值看成是指针往外多加一位，左边从-1开始，右边则是列表长度（不用减掉1），如此处理便可以取到两个边界值，代码如下：

def binary_serch(array, target):
    l = -1
    r = len(array)

    i = 1
    while l + 1 != r:         # 左右索引相差1时跳出循环
        m = int(0.5*l+0.5*r)
        guess = array[m]
        if guess > target:
            r = m
            print('太大了！%d:%d' % (m, guess))  # 打印对应的索引和元素
        elif guess < target:
            l = m
            print('太小了！%d:%d' % (m, guess))  # 打印对应的索引和元素
        else:
            print('猜对了！值为%d，总执行%d次。' % (target, i))
            break
        i += 1

if __name__ == '__main__':
    array = [i for i in range(1, 101)]  # 有序数组
    binary_serch(array, 1)
    binary_serch(array, 100)

该代码和我一开是写的代码有三句有一定的差别，分别是第2行、第3行和第6行：

一开始我的那个代码就是因为取不到一边的边界值，所以该解决方案在两边多加一位，如此一来便可以取到整个列表的所有值。当然，在单独看索引值的取值的情况下，该方案也是取不到索引值100的，还是会出现一开始的那个问题int((99+100)/2)=99，永远取不到100，但是我们的取值范围在0~99，所以不用取到两个索引的边界值-1和100。而取到0和99的时候，-1和0、100和99都相差1，所以引出了while循环的条件l + 1 != r，即当左右索引值二者相差1的时候跳出循环。

理论上，该条件还可以防止出现溢出现象（即：IndexError: list index out of range）导致报错。其实在猜测值等于目标值的时候，便会break，所以在该逻辑下不会存在溢出现象。所以循环的条件稍微取大一些也不会对结果造成影响，如while l < r:或while l <= r:。

在该逻辑下，l < r比l + 1 != r多了一种可能性：l + 1 == r，而l <= r比l < r也多了一种可能性l == r。由于二分法在左右相差1（即l + 1 == r）之前就已经可以取到所有的值并会触发break，所以判断条件并不会执行到l + 1 == r和l == r。
尽管如此，还是推荐使用l + 1 != r，因为在需求变种时很有效。

注意点：由于题目一开始就限定了输入的目标值是在数组范围内，所以没有做判断大于数组最大值和小于数组最小值的情况，实际应用或需要，如下需求变种便需要考虑，以避免取值时出现溢出现象。

三、需求变种

需求1：查找第一个大于某值的值
当左索引和有索引相差1时，跳出循环，取右索引值对应的元素。

def binary_serch(array, target):
    l = -1
    r = len(array)

    while l + 1 != r:         # 左右索引相差1时跳出循环
        m = int(0.5*l+0.5*r)
        guess = array[m]
        if guess > target:
            r = m
            print('较大，往左边移动。%d:%d' % (m, guess))  # 打印对应的索引和元素
        elif guess < target:
            l = m
            print('较小，往右边移动。%d:%d' % (m, guess))  # 打印对应的索引和元素
        else:
            l = m  # 取第一个大于某值的值，当相等的时候，需要继续往右边取，所以m赋值给左索引
            print('相等，继续往右边取值。%d:%d' % (m, guess))  # 打印对应的索引和元素
    # 判断不小于数组最大值
    if target >= max(array):
        print('无符合值，目标值不小于数组内最大值。')
    else:
        print(array[r])

if __name__ == '__main__':
    array = [1, 3, 5, 5, 5, 7, 9]  # 有序数组
    # 分别测试数组内的值
    # for i in array:
    #     binary_serch(array, i)
    #     print('原来的值%d' % i)
    binary_serch(array, 0)   # 预期结果1
    binary_serch(array, 10)  # 预期结果无符合值

需求2：查找最后一个小于某值的值
当左索引和有索引相差1时，跳出循环，取左索引值对应的元素。

def binary_serch(array, target):
    l = -1
    r = len(array)

    while l + 1 != r:         # 左右索引相差1时跳出循环
        m = int(0.5*l+0.5*r)
        guess = array[m]
        if guess > target:
            r = m
            print('较大，往左边移动。%d:%d' % (m, guess))  # 打印对应的索引和元素
        elif guess < target:
            l = m
            print('较小，往右边移动。%d:%d' % (m, guess))  # 打印对应的索引和元素
        else:
            r = m  # 取最后一个小于某值的值，当相等的时候，需要继续往左边取，所以m赋值给右索引
            print('相等，继续往左边取值。%d:%d' % (m, guess))  # 打印对应的索引和元素

    if target <= min(array):
        print('无符合值，目标值不大于数组内最小值。')
    else:
        print(array[l])

if __name__ == '__main__':
    array = [1, 3, 5, 5, 5, 7, 9]  # 有序数组
    # 分别测试数组内的值
    for i in array:
        binary_serch(array, i)
        print('原来的值%d' % i)
    binary_serch(array, 0)   # 预期结果无符合值
    binary_serch(array, 10)  # 预期结果9