title: Inserting element into sorted vector
body: <p>I wrote a C++ program with the goal of quickly inserting an element into a sorted vector. It works sometimes but not all of the time and I have not been able to figure out why. When I follow the algorithm with a paper and pencil it works out but something is wrong. Please help?</p>
  
  <pre><code>#include &lt;time.h&gt;
  #include &lt;cstdlib&gt;
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  using namespace std;
  
  vector&lt;int&gt; sortedVec;
  
  int main() {
      // Random seed
      srand(time(NULL));
  
      // Put in n random elements
      for (int i = 0; i &lt; 10; i++) sortedVec.push_back(rand()%10);
  
      // Sort the vector
      bool swapped = true;
      int endDecrement = 0;
      while (swapped) {
          swapped = false;
          endDecrement++;
          for (int i = 0; i &lt; sortedVec.size()-endDecrement; i++) {
              if (sortedVec.at(i) &gt; sortedVec.at(i+1)) {
                  int swap = sortedVec.at(i);
                  sortedVec.at(i) = sortedVec.at(i+1);
                  sortedVec.at(i+1) = swap;
                  swapped = true;
              }
          }
      }
  
      cout&lt;&lt;"Sorted random list:"&lt;&lt;endl;
      for (int i = 0; i &lt; sortedVec.size(); i++) cout&lt;&lt;sortedVec.at(i)&lt;&lt;endl;
  
      int toInsert = rand()%10;
      cout&lt;&lt;"Random element to insert = "&lt;&lt;toInsert&lt;&lt;endl;
  
      // Insert a random int to the sorted vector
      int minIndex = 0;
      int maxIndex = sortedVec.size()-1;
      while (true) {
          int mid = (maxIndex-minIndex)&gt;&gt;1;
          if (toInsert == sortedVec.at(mid) || maxIndex-minIndex &lt; 2) {
              sortedVec.insert(sortedVec.begin()+mid, toInsert);
              break;
          }
          else if (toInsert &lt; sortedVec.at(mid)) maxIndex = mid;
          else if (toInsert &gt; sortedVec.at(mid)) minIndex = mid;
      }
  
      cout&lt;&lt;"Random list with inserted element:"&lt;&lt;endl;
      for (int i = 0; i &lt; sortedVec.size(); i++) cout&lt;&lt;sortedVec.at(i)&lt;&lt;endl;
  
      return 0;
  }
  </code></pre>