<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"
lang="en" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>
lower_bound [C++ Reference]
</title>
<meta name="generator" content="DokuWiki Release 2009-12-25c "Lemming"" />
<meta name="robots" content="index,follow" />
<meta name="date" content="2010-04-22T21:30:53-0700" />
<meta name="keywords" content="stl,algorithm,lower_bound" />
<link rel="search" type="application/opensearchdescription+xml" href="/wiki/lib/exe/opensearch.php" title="C++ Reference" />
<link rel="start" href="/wiki/" />
<link rel="contents" href="/wiki/stl/algorithm/lower_bound?do=index" title="Index" />
<link rel="alternate" type="application/rss+xml" title="Recent Changes" href="/wiki/feed.php" />
<link rel="alternate" type="application/rss+xml" title="Current Namespace" href="/wiki/feed.php?mode=list&ns=stl:algorithm" />
<link rel="edit" title="Edit this page" href="/wiki/stl/algorithm/lower_bound?do=edit" />
<link rel="alternate" type="text/html" title="Plain HTML" href="/wiki/_export/xhtml/stl/algorithm/lower_bound" />
<link rel="alternate" type="text/plain" title="Wiki Markup" href="/wiki/_export/raw/stl/algorithm/lower_bound" />
<link rel="canonical" href="http://www.cppreference.com/wiki/stl/algorithm/lower_bound" />
<link rel="stylesheet" media="all" type="text/css" href="/wiki/lib/exe/css.php?s=all&t=custom1&tseed=1272971091" />
<link rel="stylesheet" media="screen" type="text/css" href="/wiki/lib/exe/css.php?t=custom1&tseed=1272971091" />
<link rel="stylesheet" media="print" type="text/css" href="/wiki/lib/exe/css.php?s=print&t=custom1&tseed=1272971091" />
<script type="text/javascript" charset="utf-8" ><!--//--><![CDATA[//><!--
var NS='stl:algorithm';var JSINFO = {"id":"stl:algorithm:lower_bound","namespace":"stl:algorithm"};
//--><!]]></script>
<script type="text/javascript" charset="utf-8" src="/wiki/lib/exe/js.php?tseed=1272971091" ></script>
<link rel="shortcut icon" href="/wiki/lib/tpl/custom1/images/favicon.png" />
</head>
<body>
<div class="dokuwiki">
<div class="stylehead">
<div class="header">
<div class="pagename">
[[<a href="../../stl/algorithm/lower_bound.html" title="Backlinks">lower_bound</a>]]
</div>
<div class="logo">
<a href="http://www.cppreference.com" name="dokuwiki__top" id="dokuwiki__top" accesskey="h" title="[ALT+H]">C++ Reference</a> </div>
<div class="clearer"></div>
</div>
<div class="breadcrumbs">
<span class="bchead">You are here: </span><a href="../../start.html" title="start">C++ Reference</a> » <a href="../../stl/start.html" title="stl:start">C++ Standard Template Library</a> » <a href="../../stl/algorithm/start.html" title="stl:algorithm:start">C++ Algorithms</a> » <a href="../../stl/algorithm/lower_bound.html" title="stl:algorithm:lower_bound">lower_bound</a> </div>
</div>
<div class="plugin_translation"><span>Translations of this page<sup><a href="../../localization.html" class="wikilink1" title="localization">?</a></sup>:</span> <ul> <li><div class="li"><span class="curid"><a href="../../stl/algorithm/lower_bound.html" class="wikilink1" title="stl:algorithm:lower_bound">en</a></span></div></li> <li><div class="li"><a href="../../br-pt/stl/algorithm/lower_bound.html" class="wikilink2" title="br-pt:stl:algorithm:lower_bound" rel="nofollow">br-pt</a></div></li> <li><div class="li"><a href="../../cn/stl/algorithm/lower_bound.html" class="wikilink2" title="cn:stl:algorithm:lower_bound" rel="nofollow">cn</a></div></li> <li><div class="li"><a href="../../cz/stl/algorithm/lower_bound.html" class="wikilink2" title="cz:stl:algorithm:lower_bound" rel="nofollow">cz</a></div></li> <li><div class="li"><a href="../../de/stl/algorithm/lower_bound.html" class="wikilink2" title="de:stl:algorithm:lower_bound" rel="nofollow">de</a></div></li> <li><div class="li"><a href="../../es/stl/algorithm/lower_bound.html" class="wikilink2" title="es:stl:algorithm:lower_bound" rel="nofollow">es</a></div></li> <li><div class="li"><a href="../../fr/stl/algorithm/lower_bound.html" class="wikilink2" title="fr:stl:algorithm:lower_bound" rel="nofollow">fr</a></div></li> <li><div class="li"><a href="../../it/stl/algorithm/lower_bound.html" class="wikilink2" title="it:stl:algorithm:lower_bound" rel="nofollow">it</a></div></li> <li><div class="li"><a href="../../jp/stl/algorithm/lower_bound.html" class="wikilink2" title="jp:stl:algorithm:lower_bound" rel="nofollow">jp</a></div></li> <li><div class="li"><a href="../../nl/stl/algorithm/lower_bound.html" class="wikilink2" title="nl:stl:algorithm:lower_bound" rel="nofollow">nl</a></div></li> <li><div class="li"><a href="../../pl/stl/algorithm/lower_bound.html" class="wikilink2" title="pl:stl:algorithm:lower_bound" rel="nofollow">pl</a></div></li> <li><div class="li"><a href="../../ro/stl/algorithm/lower_bound.html" class="wikilink2" title="ro:stl:algorithm:lower_bound" rel="nofollow">ro</a></div></li> <li><div class="li"><a href="../../ru/stl/algorithm/lower_bound.html" class="wikilink2" title="ru:stl:algorithm:lower_bound" rel="nofollow">ru</a></div></li> <li><div class="li"><a href="../../sk/stl/algorithm/lower_bound.html" class="wikilink2" title="sk:stl:algorithm:lower_bound" rel="nofollow">sk</a></div></li> <li><div class="li"><a href="../../tr/stl/algorithm/lower_bound.html" class="wikilink2" title="tr:stl:algorithm:lower_bound" rel="nofollow">tr</a></div></li> <li><div class="li"><a href="../../tw/stl/algorithm/lower_bound.html" class="wikilink2" title="tw:stl:algorithm:lower_bound" rel="nofollow">tw</a></div></li></ul></div>
<div class="page">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-2828341-1";
urchinTracker();
</script>
<!-- wikipage start -->
<h2><a name="lower_bound" id="lower_bound">lower_bound</a></h2>
<div class="level2">
<p>
Syntax:
</p>
<pre class="c code c++" style="font-family:monospace;"> <span class="co2">#include <algorithm></span>
forward_iterator lower_bound<span class="br0">(</span> forward_iterator first<span class="sy0">,</span> forward_iterator last<span class="sy0">,</span> <span class="kw4">const</span> TYPE<span class="sy0">&</span> val <span class="br0">)</span><span class="sy0">;</span>
forward_iterator lower_bound<span class="br0">(</span> forward_iterator first<span class="sy0">,</span> forward_iterator last<span class="sy0">,</span> <span class="kw4">const</span> TYPE<span class="sy0">&</span> val<span class="sy0">,</span> CompFn f <span class="br0">)</span><span class="sy0">;</span></pre>
<p>
The lower_bound() function is a type of binary_search(). This function searches
for the first place that val can be inserted into the ordered range defined by
first and last that will not mess up the existing ordering; or,
equivalently, it returns the iterator to the first element that is not less than val,
or “end” if all elements are less than val. This function
requires the elements to be in order.
</p>
<p>
The return value of lower_bound() is an iterator that points to the location
where val can be safely inserted. Unless the comparison function f is
specified, the < operator is used for ordering.
</p>
<p>
For example, the following code uses lower_bound() to insert the number 7 into
an ordered vector of integers:
</p>
<pre class="c code c++" style="font-family:monospace;"> vector<span class="sy0"><</span>int<span class="sy0">></span> nums<span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> <span class="sy0">-</span>242 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> <span class="sy0">-</span>1 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> 0 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> 5 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> 8 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> 8 <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">push_back</span><span class="br0">(</span> 11 <span class="br0">)</span><span class="sy0">;</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> <span class="st0">"Before nums is: "</span><span class="sy0">;</span>
<span class="kw1">for</span><span class="br0">(</span> <span class="kw4">unsigned</span> <span class="kw4">int</span> i <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> i <span class="sy0"><</span> nums.<span class="me1">size</span><span class="br0">(</span><span class="br0">)</span><span class="sy0">;</span> i<span class="sy0">++</span> <span class="br0">)</span> <span class="br0">{</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> nums<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0"><<</span> <span class="st0">" "</span><span class="sy0">;</span>
<span class="br0">}</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> endl<span class="sy0">;</span>
vector<span class="sy0"><</span>int<span class="sy0">>::</span><span class="me2">iterator</span> result<span class="sy0">;</span>
<span class="kw4">int</span> new_val <span class="sy0">=</span> <span class="nu0">7</span><span class="sy0">;</span>
result <span class="sy0">=</span> lower_bound<span class="br0">(</span> nums.<span class="me1">begin</span><span class="br0">(</span><span class="br0">)</span><span class="sy0">,</span> nums.<span class="me1">end</span><span class="br0">(</span><span class="br0">)</span><span class="sy0">,</span> new_val <span class="br0">)</span><span class="sy0">;</span>
nums.<span class="me1">insert</span><span class="br0">(</span> result<span class="sy0">,</span> new_val <span class="br0">)</span><span class="sy0">;</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> <span class="st0">"After, nums is: "</span><span class="sy0">;</span>
<span class="kw1">for</span><span class="br0">(</span> <span class="kw4">unsigned</span> <span class="kw4">int</span> i <span class="sy0">=</span> <span class="nu0">0</span><span class="sy0">;</span> i <span class="sy0"><</span> nums.<span class="me1">size</span><span class="br0">(</span><span class="br0">)</span><span class="sy0">;</span> i<span class="sy0">++</span> <span class="br0">)</span> <span class="br0">{</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> nums<span class="br0">[</span>i<span class="br0">]</span> <span class="sy0"><<</span> <span class="st0">" "</span><span class="sy0">;</span>
<span class="br0">}</span>
<a href="http://www.opengroup.org/onlinepubs/009695399/functions/cout.html"><span class="kw3">cout</span></a> <span class="sy0"><<</span> endl<span class="sy0">;</span></pre>
<p>
The above code produces the following output:
</p>
<pre class="code">
Before nums is: -242 -1 0 5 8 8 11
After, nums is: -242 -1 0 5 7 8 8 11</pre>
<p>
lower_bound() runs in <a href="../../complexity.html" class="wikilink1" title="complexity">logarithmic time</a> for containers that support random access, and in linear time for all other containers. It always makes O(log n) comparisons, though.
</p>
<p>
Related Topics: <a href="../../stl/algorithm/binary_search.html" class="wikilink1" title="stl:algorithm:binary_search">binary_search</a>, <a href="../../stl/algorithm/equal_range.html" class="wikilink1" title="stl:algorithm:equal_range">equal_range</a>, <a href="../../stl/algorithm/upper_bound.html" class="wikilink1" title="stl:algorithm:upper_bound">upper_bound</a>
</p>
</div>
<div class="secedit"><form class="button btn_secedit" method="post" action="/wiki/stl/algorithm/lower_bound"><div class="no"><input type="hidden" name="do" value="edit" /><input type="hidden" name="lines" value="3-" /><input type="hidden" name="rev" value="1271997053" /><input type="submit" value="Edit" class="button" title="lower_bound" /></div></form></div>
<!-- wikipage stop -->
</div>
<div class="clearer"> </div>
<div class="stylefoot">
<div class="meta">
<div class="user">
</div>
<!--
<div class="doc">
stl/algorithm/lower_bound.txt · Last modified: 04/22/2010 21:30 by 189.71.254.172 </div>
-->
</div>
<div class="bar" id="bar__bottom">
<div class="bar-left" id="bar__bottomleft">
<a href="../../stl/algorithm/lower_bound.html" class="action edit" accesskey="e" rel="nofollow">Edit this page</a> •
<a href="../../stl/algorithm/lower_bound.html" class="action revisions" accesskey="o" rel="nofollow">Old revisions</a> </div>
<div class="bar-right" id="bar__bottomright">
•
•
•
<a href="../../stl/algorithm/lower_bound.html" class="action login" rel="nofollow">Login</a> •
<a href="../../stl/algorithm/lower_bound.html" class="action index" accesskey="x" rel="nofollow">Index</a> •
<a href="../../stl/algorithm/lower_bound.html" class="action recent" accesskey="r" rel="nofollow">Recent changes</a> •
<a href="../../feed.php.html" title="Recent changes RSS feed">RSS</a> •
<a href='http://creativecommons.org/licenses/by/3.0/us/' title='Creative Commons license'>cc</a> •
<form action="/wiki/" accept-charset="utf-8" class="search" id="dw__search"><div class="no"><input type="hidden" name="do" value="search" /><input type="text" id="qsearch__in" accesskey="f" name="id" class="edit" title="[ALT+F]" /><input type="submit" value="Search" class="button" title="Search" /><div id="qsearch__out" class="ajax_qsearch JSpopup"></div></div></form>
</div>
<div class="clearer"></div>
</div>
</div>
</div>
<div class="no"><img src="/wiki/lib/exe/indexer.php?id=stl%3Aalgorithm%3Alower_bound&1273196466" width="1" height="1" alt="" /></div>
</body>
</html>