?? csdn技術中心 cuj：標準庫：標準庫中的搜索算法.htm
字號:
lang=EN-US><FONT face=宋體 size=3>unguarded_find(InIter first,
</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>const T&
val)</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>{</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>while
(!(*first==val))</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes">
</SPAN>++first;</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>}</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>Knuth的線性搜索版本[注3]更接近unguarded_find()而不是std::find()。注意，unguarded_find()不是C++標準的一部分。它比find()危險，通用性上也稍差。你只能在確保有一個元素等價于val時使用它－－這通常意味著你自己已經將那個元素放在里面了，并作為區間結束的哨兵。使用哨兵并不總是成立。(如果你正在搜索的是一個只讀區間怎么辦？)但當它可用時，unguarded_find()比標準庫中的所有東西都更快，更簡單。</FONT></FONT></SPAN></P>
<H3 style="MARGIN: auto 0cm"><FONT face=宋體>二分搜索</FONT></H3>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>線性搜索很簡單，并且，對于小區間，它是最好的方法。然而，如果區間越來越長，它就不再是合理的解決方案了。在最近使用XSLT的時候，我想起這個問題。我的XSLT腳本包括了一個類似于這樣的一行：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3><x:value-of
select="/defs/data[@key=$r]"/></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT
face=宋體><SPAN lang=EN-US><FONT size=3><SPAN
style="mso-tab-count: 1">
</SPAN>我用來跑這個的XSLT引擎肯定是使用的線性搜索。我在一個list中搜索，并對list中的每個條目執行了這個搜索。我的腳本是O(N</FONT></SPAN><SUP><SPAN
lang=EN-US
style="FONT-SIZE: 15pt; mso-bidi-font-size: 10.5pt">2</SPAN></SUP><SPAN
lang=EN-US><FONT size=3>)的，它運行需要花幾分鐘。</FONT></SPAN></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>如果你正在搜索一個完全一般的區間，不能比線性搜索做得更好了。你必須檢查每一個元素，否則你漏掉的可能就是你正在尋找的。但如果你要求這個區間是以某種方式組織的，你就可以做得更好了。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>比如，你可以要求區間是已排序的。如果有一個已序區間，就可以使用線性搜索的一個改良版本(當你到達一個比所尋找的元素更大的元素時，不需要繼續到區間結束就可以知道搜索已經失敗了)，但更好的方法是使用二分搜索。通過查看區間中央的元素，你就可以說出所搜索的元素在前半部分還是后半部分；重復這個分解過程，你不需要遍歷所有元素就能找到要找的元素。線性搜索需要O(N)的比較，而二分搜索只需要O(log
N)。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>標準運行庫包含二分搜索的四個不同版本：lower_bound()，upper_bound()，equal_range()和binary_search()。他們全部都有著相同的形式：接受一個區間、一個試圖查找的元素，和可選的比較函數。區間必須是根據此比較函數進行過排序的；如果不提供比較函數，它必須是根據通常的“<”運算排序的。于是，舉例來說，如果你正在一個升序排序的int數組中搜索時，你可以使用默認行為。如果在一個降序排序的int數組中搜索時，你可以傳入一個std::greater<int>作為比較函數。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>在四個二分搜索函數中，最沒用的一個是名字最一目了然的那個：binary_search()。它所返回是簡單的yes或no：存在于區間中時返回true，否則為false。但光這么一個信息沒什么用；我從未遇到什么場合來使用binary_search()。如果你想搜索的元素存在，你可能想知道它的位置；如果不存在，你可能想知道如果它存在，這個位置是哪里。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>關于元素的位置，你可以想問幾個不同的問題，而這正是二分搜索的幾個不同版本存在的原因。當相同的元素存在好幾個拷貝時，它們的區別就很重要了。舉例來說，假如你有一個int的數組，然后使用lower_bound()和upper_bound()都找尋同一個值：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>int A[10] = </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>{ 1, 2, 3, 5, 5, 5, 5, 7, 8,
9 };</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>int* first = </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>std::lower_bound(A+0, A+10,
5);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>int* last<SPAN
style="mso-spacerun: yes"> </SPAN>= </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>std::upper_bound(A+0, A+10,
5);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>名字first和last暗示了區別：lower_bound()返回第一個你正在尋找的數值(對本例，是&A[3])，而upper_bound()返回最后一個你正尋找的值的下一個的iterator(對本例，是&A[7])。如果你搜索的值不存在，你將得到如果它存在的話，應該位于的位置。和前面一樣，我們可以寫：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>int* first = </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>std::lower_bound(A+0, A+10,
6);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>int* last<SPAN
style="mso-spacerun: yes"> </SPAN>= </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>std::upper_bound(A+0, A+10,
6);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>first和last都將等于&A[7]，因為這是6在不違背排序時可以插入的唯一位置。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>實踐中，你看不到lower_bound()的調用后面立即跟一個upper_bound()。如果你同時需要這兩個信息，那正是引入最后一個二分搜索算法的原因：equal_range()返回一個pair，第一個元素是lower_bound()將要返回的值，第二個元素是upper_bound()的返回值。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>直到此時，我在討論中故意比較粗略：我說了lower_bound()和upper_bound()找一個值，但沒有正確說明它的含義。如果你寫</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>iterator i = </FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>std::lower_bound(first,
last, x);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT size=3><FONT
face=宋體>而且搜尋成功，你保證<SPAN
lang=EN-US>*i和x相等嗎？<B>不一定！</B>lower_bound()和upper_bound()從不對等價性進行測試<B>（WQ注：邏輯相等，使用operator==()）</B>。它們使用你提供的比較函數：operator<()或其它一些功能象“less
than”的比較函數。這意味著在*i不小于x并且x不小于*i時，搜索成功<B>（WQ注，即等值性，數學相等）</B>。</SPAN></FONT></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>這個區別看起來象吹毛求疵，但它不是。假如你一些具有很多字段的復雜記錄，你使用其中的一個字段作為排序的key值（比如，人的姓）。兩個記錄可能有相同的key值，于是，即使所有其它子段都是不同的，它們哪一個也不小于另外一個。</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>一旦開始想到記錄和key值，二分搜索的另外一個問題就變得很自然了：你能用二分搜索根據key來搜索記錄嗎？更具體些，假設我們定義了一個struct
X：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>struct X {</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>int
id;</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>... // other
fields</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>};</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><FONT size=3><FONT
face=宋體>再假設有一個<SPAN
lang=EN-US>vector<X>，根據元素的id進行過排序。你如何使用二分搜索來找到一個指定id（比如148）的X？</SPAN></FONT></FONT></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>一個方法是創建一個有著指定的id啞X對象，并在二分搜索中使用它：</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>X dummy;</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體 size=3>dummy.id = 148;</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT face=宋體
size=3>vector<X>::iterator</FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes"> </SPAN>=
lower_bound(v.begin(), v.end(),</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes">
</SPAN>dummy,</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-spacerun: yes">
</SPAN>X_compare);</FONT></FONT></SPAN></P>
<P class=MsoPlainText style="MARGIN: 0cm 0cm 0pt"><SPAN
lang=EN-US><FONT size=3><FONT face=宋體><SPAN
style="mso-tab-count: 1">
</SPAN>目前而言，這是最可靠的方法。如果你關心最大程度的可移植性，它是你所應該使用的方法。另一方面，它不是非常優雅。你必須創建一個完整的X對象，雖然你需要的只是其中一個字段；其它字段不得不被初始化為默認值或隨機值。那個初始化可能是不方便的，昂貴的，或有時甚至不可能的。</FONT></FONT></SPAN></P>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -