10.2.2　二分查找

二分查找（Binary Search）算法也称为折半查找算法，把一个有序数列分割为两半，查找值跟中间值比较：若找到，则结束查找；否则，将区间范围缩小到左边区间或右边区间，再对其进行折半查找比较，直到找到对应的值或区间范围缩小到0，查找结束。其实现过程如图10.3所示。

图10.3　二分查找算法

如图10.3所示，第一次折半比较区间的左右边界下标为left=0、right=6，折半中间下标为mid=（6-0）/2=3，下标对应的值为10，需要查找的26大于10，因此需要查找的区间在右边；

第二次折半比较，左右边界下标为left=mid+1=4，right=6，求中间下标mid=（6-4）/2+4=5，该下标对应的值为26，满足查找需要，查找结束。

代码文件：10_2_2_BinarySearch.py

(https://www.daowen.com)

上述代码执行结果如下：

与线性查找相比较，二分查找效率会明显加快。如同样查找26，线性查找需要比较6次（从左到右），而二分查找仅需要比较2次。

注意

二分查找算法使用的前提条件是，队列元素必须有序排序（升序或降序），在没有有序队列里，无法使用算法（排序方法详见10.3节）。

所以，选择好的算法，可以节省运算时间。