📄 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 + -