title: How to find the insertion point in an array using binary search?
body: <p>The basic idea of binary search in an array is simple, but it might return an "approximate" index if the search fails to find the exact item. (we might sometimes get back an index for which the value is larger or smaller than the searched value).</p>
  
  <p>For looking for the exact insertion point, it seems that after we got the approximate location, we might need to "scan" to left or right for the exact insertion location, so that, say, in Ruby, we can do <code>arr.insert(exact_index, value)</code></p>
  
  <p>I have the following solution, but the handling for the part when <code>begin_index &gt;= end_index</code> is a bit messy.  I wonder if a more elegant solution can be used?</p>
  
  <p>(this solution doesn't care to scan for multiple matches if an exact match is found, so the index returned for an exact match may point to any index that correspond to the value... but I think if they are all integers, we can always search for <code>a - 1</code> after we know an exact match is found, to find the left boundary, or search for <code>a + 1</code> for the right boundary.)</p>
  
  <p>My solution:</p>
  
  <pre><code>DEBUGGING = true
  
  def binary_search_helper(arr, a, begin_index, end_index)
    middle_index = (begin_index + end_index) / 2
    puts "a = #{a}, arr[middle_index] = #{arr[middle_index]}, " +
             "begin_index = #{begin_index}, end_index = #{end_index}, " +
             "middle_index = #{middle_index}" if DEBUGGING
    if arr[middle_index] == a
      return middle_index
    elsif begin_index &gt;= end_index
      index = [begin_index, end_index].min
      return index if a &lt; arr[index] &amp;&amp; index &gt;= 0  #careful because -1 means end of array
      index = [begin_index, end_index].max
      return index if a &lt; arr[index] &amp;&amp; index &gt;= 0
      return index + 1
    elsif a &gt; arr[middle_index]
      return binary_search_helper(arr, a, middle_index + 1, end_index)
    else
      return binary_search_helper(arr, a, begin_index, middle_index - 1)
    end
  end
  
  # for [1,3,5,7,9], searching for 6 will return index for 7 for insertion
  # if exact match is found, then return that index
  def binary_search(arr, a)
    puts "\nSearching for #{a} in #{arr}" if DEBUGGING
    return 0 if arr.empty?
    result = binary_search_helper(arr, a, 0, arr.length - 1)
    puts "the result is #{result}, the index for value #{arr[result].inspect}" if DEBUGGING
    return result
  end
  
  
  arr = [1,3,5,7,9]
  b = 6
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1,3,5,7,9,11]
  b = 6
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1,3,5,7,9]
  b = 60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1,3,5,7,9,11]
  b = 60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1,3,5,7,9]
  b = -60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1,3,5,7,9,11]
  b = -60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1]
  b = -60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = [1]
  b = 60
  arr.insert(binary_search(arr, b), b)
  p arr
  
  arr = []
  b = 60
  arr.insert(binary_search(arr, b), b)
  p arr
  </code></pre>
  
  <p>and result:</p>
  
  <pre><code>Searching for 6 in [1, 3, 5, 7, 9]
  a = 6, arr[middle_index] = 5, begin_index = 0, end_index = 4, middle_index = 2
  a = 6, arr[middle_index] = 7, begin_index = 3, end_index = 4, middle_index = 3
  a = 6, arr[middle_index] = 5, begin_index = 3, end_index = 2, middle_index = 2
  the result is 3, the index for value 7
  [1, 3, 5, 6, 7, 9]
  
  Searching for 6 in [1, 3, 5, 7, 9, 11]
  a = 6, arr[middle_index] = 5, begin_index = 0, end_index = 5, middle_index = 2
  a = 6, arr[middle_index] = 9, begin_index = 3, end_index = 5, middle_index = 4
  a = 6, arr[middle_index] = 7, begin_index = 3, end_index = 3, middle_index = 3
  the result is 3, the index for value 7
  [1, 3, 5, 6, 7, 9, 11]
  
  Searching for 60 in [1, 3, 5, 7, 9]
  a = 60, arr[middle_index] = 5, begin_index = 0, end_index = 4, middle_index = 2
  a = 60, arr[middle_index] = 7, begin_index = 3, end_index = 4, middle_index = 3
  a = 60, arr[middle_index] = 9, begin_index = 4, end_index = 4, middle_index = 4
  the result is 5, the index for value nil
  [1, 3, 5, 7, 9, 60]
  
  Searching for 60 in [1, 3, 5, 7, 9, 11]
  a = 60, arr[middle_index] = 5, begin_index = 0, end_index = 5, middle_index = 2
  a = 60, arr[middle_index] = 9, begin_index = 3, end_index = 5, middle_index = 4
  a = 60, arr[middle_index] = 11, begin_index = 5, end_index = 5, middle_index = 5
  the result is 6, the index for value nil
  [1, 3, 5, 7, 9, 11, 60]
  
  Searching for -60 in [1, 3, 5, 7, 9]
  a = -60, arr[middle_index] = 5, begin_index = 0, end_index = 4, middle_index = 2
  a = -60, arr[middle_index] = 1, begin_index = 0, end_index = 1, middle_index = 0
  a = -60, arr[middle_index] = 9, begin_index = 0, end_index = -1, middle_index = -1
  the result is 0, the index for value 1
  [-60, 1, 3, 5, 7, 9]
  
  Searching for -60 in [1, 3, 5, 7, 9, 11]
  a = -60, arr[middle_index] = 5, begin_index = 0, end_index = 5, middle_index = 2
  a = -60, arr[middle_index] = 1, begin_index = 0, end_index = 1, middle_index = 0
  a = -60, arr[middle_index] = 11, begin_index = 0, end_index = -1, middle_index = -1
  the result is 0, the index for value 1
  [-60, 1, 3, 5, 7, 9, 11]
  
  Searching for -60 in [1]
  a = -60, arr[middle_index] = 1, begin_index = 0, end_index = 0, middle_index = 0
  the result is 0, the index for value 1
  [-60, 1]
  
  Searching for 60 in [1]
  a = 60, arr[middle_index] = 1, begin_index = 0, end_index = 0, middle_index = 0
  the result is 1, the index for value nil
  [1, 60]
  
  Searching for 60 in []
  [60]
  </code></pre>