C++程序设计：原理与实践（进阶篇）16.8　排序和搜索

16.8　排序和搜索

我们经常希望自己的数据是有序的。为达到这个目的，我们可以使用一个能维护顺序的数据结构，例如map或set，或进行排序。在STL中，最常见和有用的排序操作是sort()，我们已经使用过多次了。在默认情况下，sort()使用<作为排序标准，但是我们也可以提供自己的标准：

作为一个基于用户指定规则进行排序的例子，我们将介绍如何进行不考虑大小写的字符串排序：

一旦一个序列已排序，我们不再需要用f?ind()从开始位置进行搜索；我们可以利用这种序进行二分搜索。二分搜索的基本工作原理如下：

假设我们在查找值x，查看中间元素：

如果元素的值等于x，我们已经找到它！

如果元素的值小于x，则值等于x的任何元素必然位于右边，因此我们查找右半部分（在这半部分进行二分查找）。

如果元素的值大于x，则值等于x的任何元素必然位于左边，因此我们查找左半部分（在这半部分进行二分查找）。

如果我们已经到达最后一个元素（向左或向右），也没有找到x，那么没有等于值x的元素。

对于更长的序列，二分搜索比f?ind()（线性搜索）的速度更快。二分搜索的标准库算法是binary_search()和equal_range()。我们说的“更长”的含义是什么呢？这要视具体情况而定，但即使序列中只有10个元素，也足以体现出binary_search()相对于f?ind()的优势。对于一个有1000个元素的序列，binary_search()可能要比f?ind()快200倍，因为其代价为O(log2(N))，参见16.6.4节。

binary_search算法有两种变形：

这些算法要求和假设输入序列是已排序的。如果未排序，“有趣的事情”如无限循环就可能会发生。binary_search()简单地告诉我们一个值是否存在：

因此，如果我们只关心一个值是否在序列中，binary_search()是理想的。如果我们还关心找到的元素，可以使用low_bound()、upper_bound()或equal_range()（参见附录C.5.4和23.4节）。有些情况下我们关心找到的是哪个元素，原因通常是对象包含更多信息而不仅仅是一个关键字，而很多元素可能具有相同的关键字，或者是我们希望找到符合搜索标准的元素。