Python基础教程 另一个经典案例：二分查找

6.6.2 另一个经典案例：二分查找

下面来看看最后一个递归示例——二分查找算法。

你可能熟悉猜心游戏。这个游戏要求猜对对方心里想的是什么，且整个猜测过程提出的“是否”问题不能超过20个。为充分利用每个问题，你力图让每个问题的答案将可能的范围减半。例如，如果你知道对方心里想的是一个人，可能问：“你心里想的是个女人吗？”除非你有很强的第六感，不然不会一开始就问：“你心里想的是John Cleese吗？”对喜欢数字的人来说，这个游戏的另一个版本是猜数。例如，对方心里想着一个1～100的数字，你必须猜出是哪个。当然，猜100次肯定猜对，但最少需要猜多少次呢？

实际上只需猜7次。首先问：“这个数字大于50吗？”如果答案是肯定的，再问：“这个数字大于75吗？”不断将可能的区间减半，直到猜对为止。你无需过多地思考就能成功。

这种策略适用于众多其他不同的情形。一个常见的问题是：指定的数字是否包含在已排序的序列中？如果包含，在什么位置？为解决这个问题，可采取同样的策略：“这个数字是否在序列中央的右边？”如果答案是否定的，再问：“它是否在序列的第二个四分之一区间内（左半部分的右边）？”依此类推。明确数字所处区间的上限和下限，并且每一个问题都将区间分成两半。

这里的关键是，这种算法自然而然地引出了递归式定义和实现。先来回顾一下定义，确保你知道该如何做。

 如果上限和下限相同，就说明它们都指向数字所在的位置，因此将这个数字返回。

 否则，找出区间的中间位置（上限和下限的平均值），再确定数字在左半部分还是右半部分。然后在继续在数字所在的那部分中查找。

在这个递归案例中，关键在于元素是经过排序的。找出中间的元素后，只需将其与要查找的数字进行比较即可。如果要查找的数字更大，肯定在右边；如果更小，它必然在左边。递归部分为“继续在数字所在的那部分中查找”，因为查找方式与定义所指定的完全相同。（请注意，这种查找算法返回数字应该在的位置。如果这个数字不在序列中，那么这个位置上的自然是另一个数

字。）

现在可以实现二分查找了。

def search(sequence, number, lower, upper):

if lower == upper:

assert number == sequence[upper]

return upper

else:

middle = (lower + upper) // 2

if number > sequence[middle]:

return search(sequence, number, middle + 1, upper)

else:

return search(sequence, number, lower, middle)

这些代码所做的与定义完全一致：如果lower == upper，就返回upper，即上限。请注意，你假设（断言）找到的确实是要找的数字（number == sequence[upper]）。如果还未达到基线条件，就找出中间位置，确定数字在它左边还是右边，再使用新的上限和下限递归地调用search。为方

便调用，还可将上限和下限设置为可选的。为此，只需给参数lower和upper指定默认值，并在函数开头添加如下条件语句：

def search(sequence, number, lower=0, upper=None):

if upper is None: upper = len(sequence) - 1

...

现在，如果你没有提供上限和下限，它们将分别设置为序列的第一个位置和最后一个位置。下面来看看这是否可行。

然而，为何要如此麻烦呢？首先，你可使用列表方法index来查找。其次，即便你要自己实现这种功能，也可创建一个循环，让它从序列开头开始迭代，直至找到指定的数字。

确实，使用index挺好，但使用简单循环可能效率低下。前面说过，要在100个数字中找到指定的数字，只需问7次；但使用循环时，在最糟的情况下需要问100次。你可能觉得“没什么大不了的”。但如果列表包含100 000 000 000 000 000 000 000 000 000 000 000个元素（对Python列表来说，这样的长度可能不现实），使用循环也将需要问这么多次，情况开始变得“很大”了。然而，

如果使用二分查找，只需问117次。

效率非常高吧①？

提示 实际上，模块bisect提供了标准的二分查找实现。

函数式编程

至此，你可能习惯了像使用其他对象（字符串、数、序列等）一样使用函数：将其赋给变量，将其作为参数进行传递，以及从函数返回它们。在有些语言（如 scheme 和 Lisp）中，几乎所有的任务都是以这种方式使用函数来完成的。在 Python 中，通常不会如此倚重函数（而是创建自定义对象，这将在下一章详细介绍），但完全可以这样做。Python提供了一些有助于进行这种函数式编程的函数： map、 filter和reduce。在较新的Python版本中，函数map和filter的用途并不大，应该使用列表推导来替代它们。你可使用map将序列的所有元素传递给函数。

>>> list(map(str, range(10))) # 与[str(i) for i in range(10)]等价

['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

你可使用filter根据布尔函数的返回值来对元素进行过滤。

>>> def func(x):

... return x.isalnum()

...

>>> seq = ["foo", "x41", "?!", "***"]

>>> list(filter(func, seq))

['foo', 'x41']

就这个示例而言，如果转而使用列表推导，就无需创建前述自定义函数。

>>> [x for x in seq if x.isalnum()]

['foo', 'x41']

实际上， Python提供了一种名为lambda表达式①的功能，让你能够创建内嵌的简单函数（主要供map、 filter和reduce使用）。

>>> filter(lambda x: x.isalnum(), seq)

['foo', 'x41']

然而，使用列表推导的可读性不是更高吗？

要使用列表推导来替换函数reduce不那么容易，而这个函数提供的功能即便能用到，也用得不多。它使用指定的函数将序列的前两个元素合二为一，再将结果与第3个元素合二为一，依此类推，直到处理完整个序列并得到一个结果。例如，如果你要将序列中的所有数相加，可结合使用reduce和lambda x, y: x+y②。

>>> numbers = [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]

>>> from functools import reduce

>>> reduce(lambda x, y: x + y, numbers)

1161

当然，就这个示例而言，还不如使用内置函数sum。