本文共 1451 字，大约阅读时间需要 4 分钟。

一、二分法查找

在有序数列中查找特定数字，顺序查找无疑效率极低。直接从数列中间开始，比较目标数字与中间值。如果中间值小于目标数字，说明目标数字位于后半段；反之，则位于前半段。这一过程不断缩小查找范围，直至找到目标数字或确定其不存在。

二、输出结果

通过上述方法，可以快速定位数列中的特定数字。下图展示了二分查找的基本原理。

三、代码实现

以下是实现二分查找的代码示例：

import random
import time
def randomList(n):
    iList = []
    for i in range(n):
        iList.append(random.randrange(0, 1000))
    return iList
def quicksort(iList):
    if len(iList) <= 1:
        return iList
    left = []
    right = []
    for i in iList[1:]:
        if i <= iList[0]:
            left.append(i)
        else:
            right.append(i)
    return quicksort(left) + [iList[0]] + quicksort(right)
def sequentialSearch(iList, key):
    ilen = len(iList)
    for i in range(ilen):
        if iList[i] == key:
            return i
    return -1
def binarySearch(iList, key):
    ilen = len(iList)
    right = ilen - 1
    left = 0
    while left <= right:
        mid = (left + right) // 2
        if key > iList[mid]:
            left = mid + 1
        elif key < iList[mid]:
            right = mid - 1
        else:
            return mid
    return -1
if __name__ == "__main__":
    iList = quicksort(randomList(20))
    keys = [random.choice(iList), random.randrange(min(iList), max(iList))]
    for key in keys:
        num = binarySearch(iList, key)
        if num != -1:
            print("%d found at position %d" % (key, num))
        else:
            print("%d not found in list" % key)

上述代码实现了二分查找和顺序查找两种方法。通过实验可以发现，二分查找的效率远高于顺序查找。