计算机科学导论：跨学科方法

4.2　排序和搜索

排序问题旨在将数组中的元素重新排列成升序。在许多计算和应用中，这是一个常用且关键的任务：音乐库中的歌曲按字母顺序排列；电子邮件按接收时间的相反顺序显示等。把事物按某种顺序排列是一种很自然的需求。排序非常有用的一个理由是，在排序的列表中搜索某些内容，要比在未排序的列表中容易得多。这种需求在计算中尤为突出，因为计算中要搜索的数组可能十分巨大，而高效的搜索可能是一个问题解决方案中的关键因素。

排序和查找对于商业应用程序（企业按照顺序存储客户文件）和科学应用程序（组织数据和计算）非常重要，并且在其他可能看似与事物排序无关的领域中也有各种应用，包括数据压缩、计算机图形学、生物信息学、数值计算、组合优化、密码学等。

我们使用这些基本问题来阐述一个观念，那就是高效的算法是计算问题的有效解决方案的关键之一。事实上，科学家已经提出了许多不同的排序和查找方法。解决一个具体任务时，我们应该选择哪种算法呢？这是一个非常重要的问题，因为不同的算法在性能上有显著的差异，从而导致成功解决实际问题还是根本无法解决实际问题的差别（即使使用最快的计算机）。

在本节中，我们将详细讨论用于查找和排序的两个经典算法——二分查找和归并排序，以及若干侧重效率的应用程序。通过这些例子，你会意识到，在解决需要大量计算的问题时，不仅仅需要注重方法的有效性，还需要注意运行成本。

二分查找法　“20个问题”的游戏（见程序1.5.2）为计算问题设计高效算法提供了一个重要并且有用的思路。规则十分很简单：你的任务是猜测一个神秘整数的值，它在0到n-1这n个整数之中。每次你做出一个猜测时，程序会告知猜测的值等于、大于或者小于那个神秘数字。为了阐述得更加清楚，我们首先稍微修改一下游戏的提问形式：“请问该数大于或等于x吗？”，其答案仅为true或false，假设n是2的整数次幂。 ...