📄 bin_2092.htm
字号:
<HTML><HEAD><TITLE>14.5 Binary Search</TITLE></HEAD><BODY><A HREF="ug1.htm"><IMG SRC="images/banner.gif"></A><BR><A HREF="nth_1433.htm"><IMG SRC="images/prev.gif"></A><A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="mer_3553.htm"><IMG SRC="images/next.gif"></A><BR><STRONG>Click on the banner to return to the user guide home page.</STRONG><H2>14.5 Binary Search</H2><P>The standard library provides a number of different variations on binary search algorithms. All will perform only approximately <SAMP>log n</SAMP> comparisons, where <SAMP>n</SAMP> is the number of elements in the range described by the arguments. The algorithms work best with random access iterators, such as those generated by vectors or deques, when they will also perform approximately <SAMP>log n</SAMP> operations in total. However, they will also work with non-random access iterators, such as those generated by lists, in which case they will perform a linear number of steps. Although legal, it is not necessary to perform a binary search on a <A HREF="../stdlibcr/set_1649.htm"><B><I>set</I></B></A> or <A HREF="../stdlibcr/mul_0958.htm"><B><I>multiset</I></B></A> data structure, since those container classes provide their own search methods, which are more efficient.</P><A NAME="idx172"><!></A><P>The generic algorithm <SAMP>binary_search()</SAMP> returns<SAMP> true</SAMP> if the sequence contains a value that is equivalent to the argument. Recall that to be equivalent means that both <SAMP>Compare(value, arg)</SAMP> and <SAMP>Compare(arg, value)</SAMP> are false. The algorithm is declared as follows:</P><PRE>bool binary_search (ForwardIterator first, ForwardIterator last, const T & value [, Compare ] );</PRE><P>In other situations it is important to know the position of the matching value. This information is returned by a collection of algorithms, defined as follows:</P><PRE> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value [ , Compare ] ); ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value [, Compare ] ); pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& value [, Compare ] );</PRE><A NAME="idx173"><!></A><P>The algorithm <SAMP>lower_bound()</SAMP> returns, as an iterator, the first position into which the argument could be inserted without violating the ordering, whereas the algorithm <SAMP>upper_bound()</SAMP> finds the last such position. These will match only when the element is not currently found in the sequence. Both can be executed together in the algorithm <SAMP>equal_range(),</SAMP> which returns a pair of iterators.</P><P>Our example program shows these functions being used with a vector of random integers.</P><PRE>void binary_search_example () // illustrate the use of the binary search algorithm{ // make an ordered vector of 15 random integers vector<int> aVec(15); generate (aVec.begin(), aVec.end(), randomValue); sort (aVec.begin(), aVec.end()); // see if it contains an eleven if (binary_search (aVec.begin(), aVec.end(), 11)) cout << "contains an 11" << endl; else cout << "does not contain an 11" << endl; // insert an 11 and a 14 vector<int>::iterator where; where = lower_bound (aVec.begin(), aVec.end(), 11); aVec.insert (where, 11); where = upper_bound (aVec.begin(), aVec.end(), 14); aVec.insert (where, 14);}</PRE><HR><A HREF="nth_1433.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc1.htm"><IMG SRC="images/toc.gif"></A><A HREF="tindex1.htm"><IMG SRC="images/tindex.gif"></A><A HREF="mer_3553.htm"><IMG SRC="images/next.gif"></A><P>©Copyright 1996, Rogue Wave Software, Inc.</P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -