title: insert an element into a sorted array using binary search
body: <p>I want to insert an element in a sorted array (replacing an existing element)</p>
  
  <pre><code>[1, 2, 3, 4, 5]
  </code></pre>
  
  <p>for example to insert 0 and maintain the order it should replace 1</p>
  
  <pre><code>[0, 2, 3, 4, 5]
  </code></pre>
  
  <p>and to insert 6 and maintain the order it should replace 5</p>
  
  <pre><code>[0, 2, 3, 4, 6]
  </code></pre>
  
  <p>I want to use binary search and I created the following</p>
  
  <pre><code>int binary_search(int *a, int first, int last, int x) {
  
      int mid;
  
      while (first &lt;= last) { /* was &lt;, changed to &lt;= */
  
          mid = (first + last) / 2;
  
          if (a[mid] == x)
              return mid;
  
          else if (a[mid] &gt; x)
              last =  mid - 1;
  
          else
              first = mid + 1;
      }
  
      /* after the loop =&gt; first = last */
  
      if (a[first] &gt; x)
          return first;
      else
          return first + 1;
  }
  </code></pre>
  
  <p>Am I missing something and How do I prove that what I did leads to an always correct result?</p>