title: O(log n) algorithm to find best insert position in sorted array
body: <p>I'm trying to make an algorithm that finds the best position to insert the <em>target</em> into the already sorted array.</p>
  
  <p>The goal is to either return the position of the item if it exists in the list, else return the position it would go into to keep the list sorted.</p>
  
  <p>So say I have a list:</p>
  
  <pre><code>   0   1   2   3   4    5    6
   ---------------------------------
   | 1 | 2 | 4 | 9 | 10 | 39 | 100 |
   ---------------------------------
  </code></pre>
  
  <p>And my target item is <code>14</code>
  It should return an index position of <code>5</code></p>
  
  <p>Pseudo-code I currently have:</p>
  
  <pre><code>array = generateSomeArrayOfOrderedNumbers()
  
  number findBestIndex(target, start, end)
      mid = abs(end - start) / 2
  
      if (mid &lt; 2) 
          // Not really sure what to put here
          return start + 1 // ??
  
      if (target &lt; array[mid])
          // The target belongs on the left side of our list //
          return findBestIndex(target, start, mid - 1)
      else
          // The target belongs on the right side of our list //
          return findBestIndex(target, mid + 1, end)
  </code></pre>
  
  <p>I not really sure what to put at this point. I tried to take a binary search approach to this, but this is the best I could come up with after 5 rewrites or so.</p>