编程珠玑-错误的二分查找算法（上）

微信公众号：科文路。转发须注明出处。

源自《编程珠玑》第 2 版第 4 章，《编写正确的程序》

（上）部分主要介绍二分查找算法原理以及一些编程理念，（中）讲解测试方法，值得细读、学习、思考，（下）部分通过运行时间分析来验证算法时间复杂度。

原理

在计算机科学中，二分查找算法（binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。其时间复杂度为 O(log n)，应用很广，应是每个程序员随手就应该能写出的高效算法。

注意，该算法理应能应用于数、字符等任何可排序类型。

二分查找表面上看起来是一个递归的过程：

• （重复过程） 比较目标值（t）是否等于当前序列的中间位置（m）的值(m_val)
  • t == m_val，如果两者相等，返回索引m，查找完成
  • t > m_val，如果目标值较大，则t可能存在于m的右侧，在m的右侧重复查找过程
  • t < m_val，如果目标值较小，则t可能存在于m的左侧，在m的左侧重复查找过程
• 如果m的左侧或右侧已经没有值，则返回-1，表示没有找到

如下图所示，需要在序列中查找是否值为 4 的索引（答案为 3）。假设第一个值（1）的索引为 1：

• 先看中间位置，中间位置索引为 5、值为 7。目标值较小，在左侧重复查找过程
• 左侧（索引1~索引4）的中间位置，中间位置索引为 2、值为 3。目标值较大，在右侧重复查找过程
• 右侧（索引3~索引4）的中间位置，中间位置索引为3、值为 4。两者相等，返回索引 3，查找完成

下面是维基百科上的定义，其也阐述了算法的底层逻辑。看一看，顺便学学英语。

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

Binary search compares the target value to the middle element of the array.

• If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.
• If the search ends with the remaining half being empty, the target is not in the array.

到这里应该就可以设计程序了吧！不过在编码之前，先固化一些姿势。

编程之前

要想编写正确的程序，最好在之前做好三个准备工作：

• 把问题定义好。 如何把一个问题转化为本专业的问题，这里是程序设计问题，是非常重要的专业技能。
• 算法设计。 本文即是在搜索算法中选择了二分查找。
• 数据结构选择。 可以参考上一章《编程珠玑-从数据出发改善程序》

程序设计

以 Python 为例，从算法原理出发，这个程序可能是写成这个样子的（循环版本）

def binary_search(arr, t):
    l = 0
    r = len(arr) - 1
    while l <= r:
        m = int((r + l) / 2)  # 取整
        if arr[m] < t:
            l = m + 1   # 将搜索范围调整为 m 右侧
        elif arr[m] > t:
            r = m - 1   # 将搜索范围调整为 m 左侧 
        else:
            return m    # 找到
    return -1   # 没有找到

在图中所示的序列

arr = [1, 3, 4, 6, 7, 8, 10, 13, 14]

中查找元素 4 的索引

print(binary_search(arr, 4))
# 2

程序将打印 2，由于 Python 序列以 0 为首元素索引，所以答案索引 2、即第三个值，没有问题。

所以到这里程序设计完成了吗？正确了吗？

这个 1946 年就被提出的算法，直到 1962 年才被修正成真正没有错误的二分搜索程序。

1988年开展的一项研究显示，20本教科书里只有5本正确实现了二分搜索。

先消化消化，下一篇文章继续说。

作业

将上文的循环版本的二分搜索改成递归版本。