<!--
    Licensed to the Apache Software  Foundation (ASF) under one or more
    contributor  license agreements.  See  the NOTICE  file distributed
    with  this  work  for  additional information  regarding  copyright
    ownership.   The ASF  licenses this  file to  you under  the Apache
    License, Version  2.0 (the  License); you may  not use  this file
    except in  compliance with the License.   You may obtain  a copy of
    the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the  License is distributed on an  "AS IS" BASIS,
    WITHOUT  WARRANTIES OR CONDITIONS  OF ANY  KIND, either  express or
    implied.   See  the License  for  the  specific language  governing
    permissions and limitations under the License.

    Copyright 1999-2007 Rogue Wave Software, Inc.
-->

<HTML>
<HEAD>
<TITLE>Binary Search</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="14-3.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="14-5.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
<H2>14.4 Binary Search</H2>
<A NAME="idx356"><!></A>
<P>The C++ Standard Library provides a number of different variations on binary search algorithms.   All 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 <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>s, such as those generated by <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B>s or <B><I><A HREF="../stdlibref/deque.html">deque</A></I></B>s. In this case they  perform approximately <SAMP>log N</SAMP> operations in total. However, these algorithms also work with non-random access <B><I>iterator</I></B>s, such as those generated by <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s, in which case they perform a linear number of steps. Although possible, it is not worthwhile to perform a binary search on a <B><I><A HREF="../stdlibref/set.html">set</A></I></B> or <B><I><A HREF="../stdlibref/multiset.html">multiset</A></I></B> data structure, since those container classes provide their own search methods, which are more efficient.</P>
<A NAME="idx357"><!></A>
<P>The generic algorithm <SAMP>std::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 <SAMP>false</SAMP>. The algorithm is declared as follows:</P>

<UL><PRE>
namespace std {
  bool binary_search(ForwardIterator first, ForwardIterator last, 
                     const T&amp; value [, Compare ] );
}
</PRE></UL>
<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>

<UL><PRE>
namespace std {
  ForwardIterator lower_bound(ForwardIterator first,
     ForwardIterator last, const T&amp; value [, Compare ] );

  ForwardIterator upper_bound (ForwardIterator first, 
     ForwardIterator last, const T&amp; value [, Compare ] );

  pair&lt;ForwardIterator, ForwardIterator&gt; equal_range
     (ForwardIterator first, ForwardIterator last,
      const T&amp; value [, Compare ] );
}
</PRE></UL>
<A NAME="idx358"><!></A>
<P>The algorithm <SAMP>std::lower_bound()</SAMP> returns, as an <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>, the first position into which the argument could be inserted without violating the ordering, whereas the algorithm <SAMP>std::upper_bound()</SAMP> finds the last such position. These match only when the element is not currently found in the sequence. Both can be executed together in the algorithm <SAMP>std::equal_range()</SAMP>, which returns a pair of <B><I>iterator</I></B>s.</P>
<P>Our example program shows these functions being used with a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> of random integers.</P>

<A NAME="idx359"><!></A>
<UL><PRE>
void binary_search_example()
// illustrates the use of the binary search algorithm
// see alg7.cpp for complete source code
{
  // make an ordered vector of 15 random integers
  std::vector&lt;int&gt; aVec(15);
  std::generate(aVec.begin(), aVec.end(), randomValue);
  std::sort(aVec.begin(), aVec.end());

  // see if it contains an eleven
  if (binary_search(aVec.begin(), aVec.end(), 11))
    std::cout &lt;&lt; "contains an 11" &lt;&lt; std::endl;
  else
    std::cout &lt;&lt; "does not contain an 11" &lt;&lt; std::endl;

  // insert an 11 and a 14
  std::vector&lt;int&gt;::iterator where;
  where = std::lower_bound(aVec.begin(), aVec.end(), 11);
  aVec.insert(where, 11);

  where = std::upper_bound(aVec.begin(), aVec.end(), 14);
  aVec.insert(where, 14);
}
</PRE></UL>

<BR>
<HR>
<A HREF="14-3.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="14-5.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
    _uacct = "UA-1775151-1";
    urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->

</BODY>
</HTML>