title: Finding key corresponding to max value in c++ map
body: <p>Given a number say 'KEY' and map &lt;int, int&gt; myMap. I am trying to find a smallest key k (condition: k &lt; KEY) in the map myMap such that it's value is maximum.</p>
  <p>Example:</p>
  <pre><code>map &lt;int, int&gt; myMap = {{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}};
                               // ^^^
  int KEY = 7;
  </code></pre>
  <p>Answer is 4, since for all the keys less than 7(KEY), the key 4 and key 6 has the maximum value of 3. 4 is the smallest key.</p>
  <p>The map increases dynamically and there are several such queries with KEY.</p>
  <p>I am trying to get the {k,v} pair in O(logN) time</p>
  <p>I'm stuck after using lower_bound. Using lower bound gives me max 'k' such that k &lt; KEY. In the example above I am able to get {7,2} for KEY=7. But struggling to get to {4,3} in logN time. Is there any data structure which can help me achieve this in logN time?</p>
  <p><strong>Update:</strong></p>
  <p>I am making sure to do the updates to the map in logarithmic time as well. Integers are not exceeding 10^5. Is it possible to use some other data structure and approach (in this case it looks like dynamic programming/binary search) to solve this in logarithmic time?</p>