程序设计导论：Python语言实践

4.2.1　二分查找法

“20个问题”的游戏（参见程序1.5.2，twentyquestions.py）提供了一个为计算问题设计和使用高效算法理念的重要而有用的例子。问题十分简单：你的任务是猜测一个取值范围位于0到n - 1之间的神秘整数。每次你做出一个猜测时，程序会告知猜测的值等于、大于或小于那个神秘的整数。正如在1.5节所述，最有效的策略是猜测数值区间中间的那个数，然后使用猜测结果把包含神秘数的区间减半。

基于某种原因（将在随后阐明），我们稍微修改一下游戏的提问形式：“请问该数大于或等于m吗？”其答案仅为true或false，并假设n为2的乘幂。现在，通过最少提问数获取神秘数的有效算法（最坏的情况）是维持包含神秘数的区间，并且每一步把区间减半。更准确地说，我们使用一个半开区间（half-open interval），半开区间包含左端点但不包含右端点。我们使用符号[lo，hi)表示所有大于或等于lo但小于hi（不等于hi）的整数。开始时lo = 0、hi = n，我们使用如下的递归策略：

·基本情况：如果hi - lo等于1，则神秘数为lo。

·归约步骤：否则，询问神秘数是否大于或等于mid = (hi + lo) / 2。如果是，则继续在区间[mid，hi)中查找。否则继续在区间[lo，mid)中查找。

这种策略是二分查找法的通用问题求解算法的一个例子，二分查找法具有广泛的应用。程序4.2.1（questions.py）是二分查找法的一种实现。

程序4.2.1　二分查找法（20个问题，questions.py）

脚本程序4.2.1使用二分查找法实现和程序1.5.2同样功能的游戏程序，但角色反过来：由用户选择一个神秘数，程序猜测其值。程序带一个命令行参数k，提示用户默想一个位于0到2 ...