title: How to insert an element into a sorted vector using binary search
body: <p>Hello I have an issue where I don't know if my implementation of inserting into a vector using binary search is right.
  I have two vectors one stores class objects. The second one is the one that is suppose to be sorted. The second vector holds the indexes of the first vector, these indexes are suppose to be sorted lexicographically (small to largest). I'm trying to make my program run O(log(n)). Here it's what I have...</p>
  
  <pre><code>void Trendtracker:: add_hashtag(string ht)
  {
  
      Entry tweet;
      tweet.count = 0;
      tweet.hashtag = ht;
      if (E.empty())
      {
          E.push_back(tweet);
          S.push_back(0);
      }
  
  
      int l, m, r;
      l = 0;
      r = S.size() -1;
  
      while (l &lt; r)
      {
          m =(l+r)/2;
          if(E[S[m]].hashtag == ht)//found #1
              return;
          else if (E[S[m]].hashtag &lt; ht)// searches right
              l = m +1;
          else
              r = m-1; // searches left
  
      }
  
      if( l ==r &amp;&amp; E[S[l]].hashtag == tweet.hashtag)// found #2
          return;
  
      E.push_back(tweet);
  
      //if not found and lower than the lowest
      if(l==0 &amp;&amp; ht &lt; E[S[l]].hashtag)
      {
          //S[0]= E.size()-1;
          S.insert(S.begin(), E.size()-1);
      }
  
      // if not found but is higher than highest
      else if(l == S.size()-1 &amp;&amp; E[S[l]].hashtag &lt; ht)
      {
          S.push_back(E.size()-1);
      }
  
      // if new hashtag goes in the second index
      else if(l==0&amp;&amp; r==0 &amp;&amp; E[S[r]].hashtag&lt; ht)
      {
  
          S.insert(S.begin()+1, E.size()-1);
      }
  
      // if not found and l &amp; r are somewhere in the middle
      else
      {
  
          S.insert(S.begin()+l, E.size()-1);
      }
  }
  </code></pre>