Matthew Austern
http://www.cuj.com/experts/1911/austern.htm?topic=experts
The genius as well as the oversights in the design of the Standard C++ library surface in a simple discussion of its linear and binary search algorithms.
--------------------------------------------------------------------------------
如果你储存着一系列的元素，或许原因理由之一是因此你能够在它里面找到些对象。在一个集合中找到一个特别的条目是个很重要的问题；所有的书都会写到它。不奇怪，标准C++运行库提供了许多不同的搜索技术。
在 C++运行库中，指明一个集合的常用方法是通过iterator指示出区间。区间可以被写为[first, last)，此处，*first是区间内的第一个元素而last则指向最后一个元素的下一个。本文展示了我们如何考虑一个通用问题：给定一个区间和一个准则，找到指向第一个满足准则的元素的iterator。因为我们将区间表示为不对称的形式，于是避开了一个特殊情况：搜索失败可以返回last，没有任何元素的区间可以写为[i, i)。
线性搜索和它的变种最简单的搜索是线性搜索，或，如Knuth所称呼的，顺序搜索：依次查看每个元素，检查它是否为我们正在搜索的那个。如果区间中有N个元素，最坏的情况就需要N次比较。
标准运行库提供了线性搜索的一些版本；两个最重要的版本是find() (它接受一个区间和值x，并查找等价于x的元素)和find_if()(接受一个区间和判决条件p，并查找满足p的元素)。线性搜索的其它版本是find_first_of()(接受两个区间，[first1,last1)和[first2,last2) ，并在[first1, last1)中查找第一个等价于[first2, last2)中任何一个元素的元素]和adjacent_find()(接受单一区间，并查找第一个等价于其后继元素的元素)。
举例来说，假如，v是一个int的vector。你能用下面的代码查找第一个0：
vector<int>::iterator i =
find(v.begin(), v.end(), 0);
你也能这样查找第一个非0值：
vector<int>::iterator i =
find_if(v.begin(), v.end(),
not1(bind2nd(equal_to<int>(),
0)));
你能这样查找第一个小质数：
A[4] = { 2, 3, 5, 7 };
vector<int>::iterator i =
find_first_of(v.begin(), v.end(),
A+0, A+4);
你能这样找到第一个重复对：
vector<int>::iterator i =
adjacent_find(v.begin(), v.end());
没有任何独立版本以对区间进行逆向搜索，因为你不需要：你能用一个简单的iterator adaptor来达到相同的效果。比如，在v中找到最后一个0，可以这么写：
vector<int>::reverse_iterator i =
find(v.rbegin(), v.rend(), 0);
线性搜索是一个简单的算法，它的实现看起来没什么可讨论的。许多书(包括我的)展示了std::find()的一个简单的实现：
template <class InIter, class T>
InIter find(InIter first, InIter last,
const T& val)
{
while (first != last && !
(*first == val))
++first;
return first;
}
这的确是线性搜索算法的一个忠实的实现，满足C++标准的需求；第一个模板参数的名字，InIter，意味着实参只需要是非常弱的Input Iterator[注1]。它看起来可能是如此的简单，以致于还不如在代码中直接手写出来。虽然如此，还是有一个令人懊恼的问题：这个实现没有达到它应该的效率。循环条件很复杂，需要为取得的每个元素作两个测试。有条件的分支昂贵的，并且复杂的循环条件不会得到与简单的循环条件同样程度的优化。
问题的答案之一，并是被某些标准运行库的实作所采用[注2]，是“解开”循环，每次检查4个元素。这是比较复杂的解决方法，因为find()然后必须处理残余元素（区间不会总是4的倍数！），以及它还需要find()基于Iterator的种类进行分解－－“解开”只能工作于Random Access Iterator指示的区间，对一般情况还是需要使用老的实现。但是，“解开”是有效果的：它将对每个元素的测试的数目从2降到 1.25。它是标准库的实现人员不需要改动任何接口就能采用的技术。
你将会在讲述算法的常见书籍中看到一个不同的答案。需要对每个元素作两次测试的原因是，如果到达区间结束还没有找到所要找的元素，我们必须承认已经失败。但是如果我们碰巧所要查找的元素总是存在，搜索绝不会失败时，会怎么样？在那种情况下，为区间结束作的测试是多余的；会没有任何的理由认为搜索算法应该首先掌握区间结束的信息（there wouldn’t be any reason for the search algorithm to keep track of the end of the range in the first place）。取代std::find()，我们可以如下实现线性搜索算法：
template <class InIter, class T>
InIter
unguarded_find(InIter first,
const T& val)
{
while (!(*first==val))
++first;
}
Knuth的线性搜索版本[注3]更接近unguarded_find()而不是std::find()。注意，unguarded_find()不是C++标准的一部分。它比find()危险，通用性上也稍差。你只能在确保有一个元素等价于val时使用它－－这通常意味着你自己已经将那个元素放在里面了，并作为区间结束的哨兵。使用哨兵并不总是成立。(如果你正在搜索的是一个只读区间怎么办？)但当它可用时，unguarded_find()比标准库中的所有东西都更快，更简单。
二分搜索线性搜索很简单，并且，对于小区间，它是最好的方法。然而，如果区间越来越长，它就不再是合理的解决方案了。在最近使用XSLT的时候，我想起这个问题。我的XSLT脚本包括了一个类似于这样的一行：
<x:value-of select="/defs/data[@key=$r]"/>
我用来跑这个的XSLT引擎肯定是使用的线性搜索。我在一个list中搜索，并对list中的每个条目执行了这个搜索。我的脚本是O(N2)的，它运行需要花几分钟。
如果你正在搜索一个完全一般的区间，不能比线性搜索做得更好了。你必须检查每一个元素，否则你漏掉的可能就是你正在寻找的。但如果你要求这个区间是以某种方式组织的，你就可以做得更好了。
比如，你可以要求区间是已排序的。如果有一个已序区间，就可以使用线性搜索的一个改良版本(当你到达一个比所寻找的元素更大的元素时，不需要继续到区间结束就可以知道搜索已经失败了)，但更好的方法是使用二分搜索。通过查看区间中央的元素，你就可以说出所搜索的元素在前半部分还是后半部分；重复这个分解过程，你不需要遍历所有元素就能找到要找的元素。线性搜索需要O(N)的比较，而二分搜索只需要O(log N)。
标准运行库包含二分搜索的四个不同版本：lower_bound()，upper_bound()，equal_range()和binary_search()。他们全部都有着相同的形式：接受一个区间、一个试图查找的元素，和可选的比较函数。区间必须是根据此比较函数进行过排序的；如果不提供比较函数，它必须是根据通常的“<”运算排序的。于是，举例来说，如果你正在一个升序排序的int数组中搜索时，你可以使用默认行为。如果在一个降序排序的int数组中搜索时，你可以传入一个std::greater<int>作为比较函数。
在四个二分搜索函数中，最没用的一个是名字最一目了然的那个：binary_search()。它所返回是简单的yes或no：存在于区间中时返回true，否则为false。但光这么一个信息没什么用；我从未遇到什么场合来使用binary_search()。如果你想搜索的元素存在，你可能想知道它的位置；如果不存在，你可能想知道如果它存在，这个位置是哪里。
关于元素的位置，你可以想问几个不同的问题，而这正是二分搜索的几个不同版本存在的原因。当相同的元素存在好几个拷贝时，它们的区别就很重要了。举例来说，假如你有一个int的数组，然后使用lower_bound()和upper_bound()都找寻同一个值：
int A[10] =
{ 1, 2, 3, 5, 5, 5, 5, 7, 8, 9 };
int* first =
std::lower_bound(A+0, A+10, 5);
int* last =
std::upper_bound(A+0, A+10, 5);
名字first和last暗示了区别：lower_bound()返回第一个你正在寻找的数值(对本例，是&A[3])，而upper_bound()返回最后一个你正寻找的值的下一个的iterator(对本例，是&A[7])。如果你搜索的值不存在，你将得到如果它存在的话，应该位于的位置。和前面一样，我们可以写：
int* first =
std::lower_bound(A+0, A+10, 6);
int* last =
std::upper_bound(A+0, A+10, 6);
first和last都将等于&A[7]，因为这是6在不违背排序时可以插入的唯一位置。
实践中，你看不到lower_bound()的调用后面立即跟一个upper_bound()。如果你同时需要这两个信息，那正是引入最后一个二分搜索算法的原因：equal_range()返回一个pair，第一个元素是lower_bound()将要返回的值，第二个元素是upper_bound()的返回值。
直到此时，我在讨论中故意比较粗略：我说了lower_bound()和upper_bound()找一个值，但没有正确说明它的含义。如果你写
iterator i =
std::lower_bound(first, last, x);
而且搜寻成功，你保证*i和x相等吗？不一定！lower_bound()和upper_bound()从不对等价性进行测试（WQ注：逻辑相等，使用operator==()）。它们使用你提供的比较函数：operator<()或其它一些功能象“less than”的比较函数。这意味着在*i不小于x并且x不小于*i时，搜索成功（WQ注，即等值性，数学相等）。
这个区别看起来象吹毛求疵，但它不是。假如你一些具有很多字段的复杂记录，你使用其中的一个字段作为排序的key值（比如，人的姓）。两个记录可能有相同的key值，于是，即使所有其它子段都是不同的，它们哪一个也不小于另外一个。
一旦开始想到记录和key值，二分搜索的另外一个问题就变得很自然了：你能用二分搜索根据key来搜索记录吗？更具体些，假设我们定义了一个struct X：
struct X {
int id;
... // other fields
};
再假设有一个vector<X>，根据元素的id进行过排序。你如何使用二分搜索来找到一个指定id（比如148）的X？
一个方法是创建一个有着指定的id哑X对象，并在二分搜索中使用它：
X dummy;
dummy.id = 148;
vector<X>::iterator
= lower_bound(v.begin(), v.end(),
dummy,
X_compare);
目前而言，这是最可靠的方法。如果你关心最大程度的可移植性，它是你所应该使用的方法。另一方面，它不是非常优雅。你必须创建一个完整的X对象，虽然你需要的只是其中一个字段；其它字段不得不被初始化为默认值或随机值。那个初始化可能是不方便的，昂贵的，或有时甚至不可能的。
可能直接将id传给lower_bound()吗？也许，通过传入一个异质比较函数，它接受一个X和一个id？这个问题没有一个简单的答案。C++标准没有完全说清楚是否允许这样的异质比较函数；依我之见，对标准的最自然的读解是不允许。在现今的实践中，异质比较函数在一些实作上可行，而在另外一些上不行。另一方面，C++标准化委员会认为这是一个缺陷，并且在未来版本的标准将明确是否允许异质比较函数[注4]。
总结C++运行库还提供了其它一些形式的搜索算法。使用find()和lower_bound()，搜索只限于单个元素，但标准运行库还提供了serach()，它寻找整个子区间。比如，你可以在一个字符串中搜索一个单词：
std::string the = "the";
std::string::iterator i
= std::search(s.begin(), s.end(),
the.begin(), the.end());
返回值，i，将指向“the”在s中第一次出现的开始处－－或，和往常一样，如果“the”不存在将返回s.end()。还有一个变种以从尾部开始搜索：
std::find_end(s.begin(), s.end(),
the.begin(), the.end());
它返回一个iterator，指向“the”最后出现处的开始，而不是第一个。(如果你认为这很奇怪，search的逆向变种叫find_end()而不是search_end()，那么你并不孤独。)
搜索可以被封装入数据结构。最明显地，标准运行库的关联容器，set、multiset、map和multimap，被特别设计为根据key进行搜索将很高效[注5]。运行库的string类也提供了许多搜索用的成员函数：find()、rfind()、find_first_of()、find_last_of()、find_first_not_of()和find_last_not_of()。我建议避免使用它们。我发现这些特殊的成员函数难以记忆，因为它们拥有如此多的形式，并且接口形式与运行库的其它部分不同；无论如何，他们不会提供任何不能从find()、find_if()、search()得到的功能。
但是，如果你仍然认为看到了一些重要的省略，你是正确的！我没有提到hash表，因为标准运行库中没有hash表。我提到了search()的子区间匹配，但那当然只是模式匹配的一个特例－－标准运行库中没有正则表达式搜索或任何类似的东西。
C++标准化委员会刚刚开始考虑对标准运行库扩充，而hash表和正则表达式是未来版本的标准的优先候选者。如果你认为标准运行库缺少了什么，并且你想提交一份提议，那么现在是你应该开始准备时候了。
注[1] See Table 72 in the C++ Standard. Some of the other search algorithms, which I discuss later, rely on the stronger Forward Iterator requirements.
[2] See, for example, <www.sgi.com/tech/stl>.
[3] See “Algorithm Q,” in §6.1 of D. E. Knuth, The Art of Computer Programming, vol. 2, Sorting and Searching, Second Edition (Addison-Wesley, 1998).
[4] See <http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#270>. Dave Abrahams had the insight that enabled the proposed resolution to this issue. He pointed out that it’s possible to think of binary searches not in terms of sorting and comparisons, but in terms of partitioning: we’re given a range with the property that all elements before a certain point satisfy a condition and all elements after it fail to satisfy the condition, and we’re looking for the transition point.
[5] But these containers aren’t the most efficient choice as often as one might think. See my earlier column “Why You Shouldn’t Use set — and What You Should Use Instead,” C++ Report, April 2000.
本文地址：http://com.8s8s.com/it/it1844.htm