Python：二分查找

前提条件

    存储数据的列表或元组中的数据是排好序了的。

实现

  1. 设置两个变量，start和end表示开始坐标和末尾坐标，用来计算数组的中间坐标的值；
  2. 当中间值和需要查找的值相等的时候，即查找完成；
  3. 当需要查找的值大于中间值的时候，就将start赋值为中间坐标值，然后再次计算中间坐标值，进行比较，这样就实现了“二分”和“查找”；
  4. 当需要查找的值小于中间值的时候，就将end赋值为中间坐标值，然后再次计算中间坐标值，进行比较，这样就实现了“二分”和“查找”。

细节重点

    计算中间值时一般是：(start+end)//2，但是这样处理的时候需要注意一个容易忽略的点：

Python中整除运算是向下圆整的

所以当我们的 start=0 和 end=(列表长度-1) 时，我们列表中的最后一个元素无论怎样都是不会被遍历到的（好好想一下中值的运算和整除向下圆整的规则）。


解决方法：
    将end设置为列表的长度。即人为多设一个位置给列表的最后一个元素去当“替死鬼”。


代码示例

x = [1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 16]
length = len(x)
num = int(input('请输要查找的数：'))


def erFeng(number, start, end):
    middle = (start + end) // 2
    if x[middle] == number:
        print(middle)
    else:
        if x[middle] > number:
            erFeng(number, start, middle)
        elif x[middle] < number:
            erFeng(number, middle, end)


erFeng(num, 0, length)

这里只体现出了问题，更多细节请自己完善。