在一個集合中找到一個特別的條目是個很重要的問題，標準C++運行庫提供了許多不同的搜索技術。
在 C++運行庫中，指明一個集合的常用方法是通過iterator指示出區(qū)間。區(qū)間可以被寫為[first, last)， 此處，*first是區(qū)間內的第一個元素而last則指向最后一個元素的下一個。本文展示了我們如何考慮一個通用問題：給定一個區(qū)間和一個準則，找到指向第一個滿足準則的元素的iterator。因為我們將區(qū)間表示為不對稱的形式，于是避開了一個特殊情況：搜索失敗可以返回last，沒有任何 元素的區(qū)間可以寫為[i, i)。
線性搜索和它的變種
最簡單的搜索是線性搜索，或，如Knuth所稱呼的，順序搜索：依次查看每個元素，檢查它是否為我們正在搜索的那個。如果區(qū)間中有N個元素，最壞的情況就需要N次比較。
標準運行庫提供了線性搜索的一些版本；兩個最重要的版本是find() (它接受一個區(qū)間和值x，并查找等價于x的元素)和find_if()(接受一個區(qū)間和判決條件p，并查找滿足p的元素)。線性搜索的其它版本是 find_first_of()(接受兩個區(qū)間，[first1,last1)和[first2,last2) ，并在[first1, last1)中查找第一個等價于[first2, last2)中任何一個元素的元素)和adjacent_find()(接受單一區(qū)間，并查找第一個等價于其后繼元素的元素)。
舉例來說，假如，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());
沒有任何獨立版本以對區(qū)間進行逆向搜索，因為你不需要：你能用一個簡單的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]。它看起來可能是如此的簡單，以致于還不如在代碼中直接手寫出來。雖然如此，還是有一個令人懊惱的問題：這個實現沒有達到它應該的效率。循環(huán)條件很復雜，需要為取得的每個元素作兩個測試。有條件的分支昂貴的，并且復雜的循環(huán)條件不會得到與簡單的循環(huán)條件同樣程度的優(yōu)化。
問題的答案之一，并是被某些標準運行庫的實作所采用[注2]，是“解開”循環(huán)，每次檢查4個元素。這是比較復雜的解決方法，因為find()然后必須處理殘余元素（區(qū)間不會總是4的倍數），以及它還需要find()基于Iterator的種類進行分解－－“解開”只能工作于Random Access Iterator指示的區(qū)間，對一般情況還是需要使用老的實現。但是，“解開”是有效果的：它將對每個元素的測試的數目從2降到 1.25。它是標準庫的實現人員不需要改動任何接口就能采用的技術。
你將會在講述算法的常見書籍中看到一個不同的答案。需要對每個元素作兩次測試的原因是，如果到達區(qū)間結束還沒有找到所要找的元素，我們必須承認已經失敗。但是如果我們碰巧所要查找的元素總是存在，搜索絕不會失敗時，會怎么樣？在那種情況下，為區(qū)間結束作的測試是多余的；會沒有任何的理由認為搜索算法應該首先 掌握區(qū)間結束的信息（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時使用它－－這通常意味著你自己已經將那個元素放在里面了，并作為區(qū) 間結束的哨兵。使用哨兵并不總是成立。(如果你正在搜索的是一個只讀區(qū)間怎么辦？)但當它可用時，unguarded_find()比標準庫中的所有東西都更快，更簡單。
二分搜索
線性搜索很簡單，并且對于小區(qū)間，它是最好的方法。然而，如果區(qū)間越來越長，它就不再是合理的解決方案了。在最近使用XSLT的時候，我想起這個問題。我的XSLT腳本包括了一個類似于這樣的一行：
<x:value-of select="/defs/data[@key=$r]"/>
我用來跑這個的XSLT引擎肯定是使用的線性搜索。我在一個list中搜索，并對list中的每個條目執(zhí)行了這個搜索。我的腳本是O(N2)的，它運行需要花幾分鐘。
如果你正在搜索一個完全一般的區(qū)間，不能比線性搜索做得更好了。你必須檢查每一個元素，否則你漏掉的可能就是你正在尋找的。但如果你要求這個區(qū)間是以某種方式組織的，你就可以做得更好了。
比如，你可以要求區(qū)間是已排序的。如果有一個已序區(qū)間，就可以使用線性搜索的一個改良版本(當你到達一個比所尋找的元素更大的元素時，不需要繼續(xù)到區(qū)間結束就可以知道搜索已經失敗了)，但更好的方法是使用二分搜索。通過查看區(qū)間中央的元素，你就可以說出所搜索的元素在前半部分還是后半部分；重復這個分解過 程，你不需要遍歷所有元素就能找到要找的元素。線性搜索需要O(N)的比較，而二分搜索只需要O(log N)。
標準運行庫包含二分搜索的四個不同版本：lower_bound()，upper_bound()，equal_range()和 binary_search()。他們全部都有著相同的形式：接受一個區(qū)間、一個試圖查找的元素，和可選的比較函數。區(qū)間必須是根據此比較函數進行過排序 的；如果不提供比較函數，它必須是根據通常的“<”運算排序的。于是，舉例來說，如果你正在一個升序排序的int數組中搜索時，你可以使用默認行為。如果在一個降序排序的int數組中搜索時，你可以傳入一個std::greater<int>作為比較函數。
在四個二分搜索函數中，最沒用的一個是名字最一目了然的那個：binary_search()。它所返回是簡單的yes或no：存在于區(qū)間中時返回 true，否則為false。但光這么一個信息沒什么用；我從未遇到什么場合來使用binary_search()。如果你想搜索的元素存在，你可能想知 道它的位置；如果不存在，你可能想知道如果它存在，這個位置是哪里。
關于元素的位置，你可以想問幾個不同的問題，而這正是二分搜索的幾個不同版本存在的原因。當相同的元素存在好幾個拷貝時，它們的區(qū)別就很重要了。舉例來說，假如你有一個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暗示了區(qū)別：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注，即等值性，數學相等）。
這個區(qū)別看起來象吹毛求疵，但它不是。假如你一些具有很多字段的復雜記錄，你使用其中的一個字段作為排序的key值（比如，人的姓）。兩個記錄可能有相同的key值，于是，即使所有其它子段都是不同的，它們哪一個也不小于另外一個。
一旦開始想到記錄和key值，二分搜索的另外一個問題就變得很自然了：你能用二分搜索根據key來搜索記錄嗎？更具體些，假設我們定義了一個struct X：
struct X {
int id;
... // other fields
};
再假設有一個vector<X>，根據元素的id進行過排序。你如何使用二分搜索來找到一個指定id（比如148）的X？
一個方法是創(chuàng)建一個有著指定的id啞X對象，并在二分搜索中使用它：
X dummy;
dummy.id = 148;
vector<X>::iterator = lower_bound(v.begin(), v.end(), dummy, X_compare);
目前而言，這是最可靠的方法。如果你關心最大程度的可移植性，它是你所應該使用的方法。另一方面，它不是非常優(yōu)雅。你必須創(chuàng)建一個完整的X對象，雖然你需要的只是其中一個字段；其它字段不得不被初始化為默認值或隨機值。那個初始化可能是不方便的，昂貴的，或有時甚至不可能的。
可能直接將id傳給lower_bound()嗎？也許，通過傳入一個異質比較函數，它接受一個X和一個id？這個問題沒有一個簡單的答案。C++標準沒有 完全說清楚是否允許這樣的異質比較函數；依我之見，對標準的最自然的讀解是不允許。在現今的實踐中，異質比較函數在一些實作上可行，而在另外一些上不行。 另一方面，C++標準化委員會認為這是一個缺陷，并且在未來版本的標準將明確是否允許異質比較函數[注4]。
總結
C++運行庫還提供了其它一些形式的搜索算法。使用find()和lower_bound()，搜索只限于單個元素，但標準運行庫還提供了serach()，它尋找整個子區(qū)間。比如，你可以在一個字符串s中搜索一個單詞：
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()，那么你并不孤獨。)
搜索可以被封裝入數據結構。最明顯地，標準運行庫的關聯(lián)容器，set、multiset、map和multimap，被特別設計為根據key進行搜索將很高 效[注5]。運行庫的string類也提供了許多搜索用的成員函數：find()、rfind()、find_first_of()、 find_last_of()、find_first_not_of()和find_last_not_of()。我建議避免使用它們。我發(fā)現這些特殊的 成員函數難以記憶，因為它們擁有如此多的形式，并且接口形式與運行庫的其它部分不同；無論如何，他們不會提供任何不能從find()、find_if ()、search()得到的功能。
但是，如果你仍然認為看到了一些重要的省略，你是正確的！我沒有提到hash表，因為標準運行庫中沒有hash表。我提到了search()的子區(qū)間匹配，但那當然只是模式匹配的一個特例－－標準運行庫中沒有正則表達式搜索或任何類似的東西。
C++標準化委員會剛剛開始考慮對標準運行庫擴充，而hash表和正則表達式是未來版本的標準的優(yōu)先候選者。如果你認為標準運行庫缺少了什么，并且你想提交一份提議，那么現在是你應該開始準備時候了。