Binary search a sorted array for the correct index in which to place a new value.

readme.md

What

Why

find_insert_index.rb

class Array

  # find_insert_index -> returns the index that the value should be inserted into
  #                      to keep the array sorted
  # Arguments
  #  val     ->  any sort of value that supports comparison or...
  #  &block  ->  If you want to compare a specific field on your object you could:
  #                {|x,y| x.FIELD <=> y.FIELD }
  #              or you could sort reverse:
  #                {|x,y| y <=> x} NOTE: your review must be sorted desc. for this to work.
  def find_insert_index(val, &block)
    from = 0
    to   = self.length - 1

    while from <= to
      mid     = (from + to) / 2
      mid_val = self[mid]

      # When Ascending sorting
      # -1 if x < y
      #  0 if x == 0
      #  1 if x > y
      compare_result = if block.present?
                         yield val, mid_val
                       else
                         val <=> mid_val
                       end

      if compare_result == 0
        return mid
      elsif compare_result == -1
        to = mid - 1
      elsif compare_result ==  1
        from = mid + 1
      else
        raise "Can not use comparison result #{compare_result}"
      end
    end

    return from
  end

end

find_insert_index_test.rb

require File.join(File.dirname(File.expand_path(__FILE__)), '..', 'test_helper')

class FindInsertIndexTest < ActiveSupport::TestCase

  test "that correct indexes are calculated for an ascen array" do
    arr = [1,3,5,7]

    assert arr.find_insert_index(0) == 0
    assert arr.find_insert_index(4) == 2
    assert arr.find_insert_index(8) == arr.length
  end

  test "that corrext indexes are calculated for a desc array" do
    arr = [7,5,3,1]

    assert arr.find_insert_index(0) {|x,y|  y <=> x} == arr.length
    assert arr.find_insert_index(4) {|x,y|  y <=> x} == 2
    assert arr.find_insert_index(8) {|x,y|  y <=> x} == 0
  end

  test "correct indexes are calculated with objects and a block" do
    arr = []

    [1,3,5,7].each do |num|
      arr << OpenStruct.new(foo: num)
    end

    assert arr.find_insert_index(OpenStruct.new(foo: 0)) {|x,y|  x.foo <=> y.foo} == 0
    assert arr.find_insert_index(OpenStruct.new(foo: 4)) {|x,y|  x.foo <=> y.foo} == 2
    assert arr.find_insert_index(OpenStruct.new(foo: 8)) {|x,y|  x.foo <=> y.foo} == arr.length
  end

  test "handle trivial case correctly" do
    arr = []

    assert arr.find_insert_index(0) == 0
  end

end