5.4.二分查找

有序列表对于我们的比较是很有用的。在顺序查找中,当我们与第一个项进行比较时,如果第一个项不是我们要查找的,则最多还有 n-1 个项目。 二分查找从中间项开始,而不是按顺序查找列表。 如果该项是我们正在寻找的项,我们就完成了查找。 如果它不是,我们可以使用列表的有序性质来消除剩余项的一半。如果我们正在查找的项大于中间项,就可以消除中间项以及比中间项小的一半元素。如果该项在列表中,肯定在大的那半部分。

然后我们可以用大的半部分重复这个过程。从中间项开始,将其与我们正在寻找的内容进行比较。再次,我们找到元素或将列表分成两半,消除可能的搜索空间的另一部分。Figure 3 展示了该算法如何快速找到值 54 。完整的函数见CodeLens 3中。

5.4.二分查找.figure3

Figure 3

  1. def binarySearch(alist, item):
  2. first = 0
  3. last = len(alist)-1
  4. found = False
  5. while first<=last and not found:
  6. midpoint = (first + last)//2
  7. if alist[midpoint] == item:
  8. found = True
  9. else:
  10. if item < alist[midpoint]:
  11. last = midpoint-1
  12. else:
  13. first = midpoint+1
  14. return found
  15. testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
  16. print(binarySearch(testlist, 3))
  17. print(binarySearch(testlist, 13))

CodeLens 3

在我们继续分析之前,我们应该注意到,这个算法是分而治之策略的一个很好的例子。分和治意味着我们将问题分成更小的部分,以某种方式解决更小的部分,然后重新组合整个问题以获得结果。 当我们执行列表的二分查找时,我们首先检查中间项。如果我们正在搜索的项小于中间项,我们可以简单地对原始列表的左半部分执行二分查找。同样,如果项大,我们可以执行右半部分的二分查找。 无论哪种方式,都是递归调用二分查找函数。 CodeLens 4 展示了这个递归版本。

  1. def binarySearch(alist, item):
  2. if len(alist) == 0:
  3. return False
  4. else:
  5. midpoint = len(alist)//2
  6. if alist[midpoint]==item:
  7. return True
  8. else:
  9. if item<alist[midpoint]:
  10. return binarySearch(alist[:midpoint],item)
  11. else:
  12. return binarySearch(alist[midpoint+1:],item)
  13. testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
  14. print(binarySearch(testlist, 3))
  15. print(binarySearch(testlist, 13))

CodeLens 4

5.4.1.二分查找分析

为了分析二分查找算法,我们需要记住,每个比较消除了大约一半的剩余项。该算法检查整个列表的最大比较数是多少?如果我们从 n 项开始,大约 n/2 项将在第一次比较后留下。第二次比较后,会有约 n/4。 然后 n/8,n/16,等等。 我们可以拆分列表多少次? Table 3 帮助我们找到答案。

5.4.二分查找.table3

Table 3

当我们切分列表足够多次时,我们最终得到只有一个项的列表。 要么是我们正在寻找的项,要么不是。达到这一点所需的比较数是 i,当

5.4.二分查找 - 图3 时。 求解 i 得出 5.4.二分查找 - 图4 。 最大比较数相对于列表中的项是对数的。 因此,二分查找是 5.4.二分查找 - 图5

还需要解决一个额外的分析问题。在上面所示的递归解中,递归调用,

  1. binarySearch(alist[:midpoint],item)

使用切片运算符创建列表的左半部分,然后传递到下一个调用(同样对于右半部分)。我们上面做的分析假设切片操作符是恒定时间的。然而,我们知道 Python中的 slice 运算符实际上是

5.4.二分查找 - 图6 。这意味着使用 slice 的二分查找将不会在严格的对数时间执行。幸运的是,这可以通过传递列表连同开始和结束索引来纠正。可以像 CodeLens 3 中所做的那样计算索引。我们将此实现作为练习。

即使二分查找通常比顺序查找更好,但重要的是要注意,对于小的 n 值,排序的额外成本可能不值得。事实上,我们应该经常考虑采取额外的分类工作是否使搜索获得好处。如果我们可以排序一次,然后查找多次,排序的成本就不那么重要。然而,对于大型列表,一次排序可能是非常昂贵,从一开始就执行顺序查找可能是最好的选择。