Insert a number into an ordered array

Question

I have an array of numbers sorted either in ascending or descending order, and I want to find the index at which to insert a number while preserving the order of the array. If the array is [1, 5, 7, 11, 51] and the number to insert is 9, I would be expecting 3 so I could do [1, 5, 7, 11, 51].insert(3, 9). If the array is [49, 32, 22, 11, 10, 8, 3, 2] and the number to be inserted is 9, I would be expecting 5 so I could do [49, 32, 22, 11, 10, 8, 3, 2].insert(5, 9)

What would be the best/cleanest way to find the index at which to insert 9 in either of these two arrays while preserving the sorting of the array?

I wrote this code that works, but it's not very pretty:

array = [55, 33, 10, 7, 1]
num_to_insert = 9
index_to_insert = array[0..-2].each_with_index.map do |n, index|
  range = [n, array[index.next]].sort
  index.next if num_to_insert.between?(range[0], range[1])
end.compact.first
index_to_insert # => 3

Answer 1

Wand Maker's answer isn't bad, but it has two problems:

1. It sorts the entire array to determine whether it's ascending or descending. That's silly when all you have to do is find one element that's not equal to the one before it compare the first and last elements to determine this. That's O(n) O(1) in the worst case instead of O(n log n).

2. It uses Array#index when it should use bsearch. We can do a binary search instead of iterating over the whole array because it's sorted. That's O(log n) in the worst case instead of O(n).

I found it was clearer to split it into two methods, but you could of course turn it into one:

def search_proc(ary, n)
  case ary.first <=> ary.last
    when  1 then ->(idx) { n > ary[idx] }
    when -1 then ->(idx) { n < ary[idx] }
    else raise "Array neither ascending nor descending"
  end
end

def find_insert_idx(ary, n)
  (0...ary.size).bsearch(&search_proc(ary, n))
end

p find_insert_idx([1, 5, 7, 11, 51], 9)
#=> 3

p find_insert_idx([49, 32, 22, 11, 10, 8, 3, 2], 9)
#=> 5

(I use Range#bsearch here. Array#bsearch works the same, but it was more convenient to use a range to return an index, and more efficient since otherwise we'd have to do each_with_index.to_a or something.)

Answer 2

This is not a good way, but perhaps cleaner since you can use the method insert_sorted(number) on either an ascending or descending array without bothering about the index it will be placed on:

module SortedInsert
  def insert_index(number)
    self.each_with_index do |element, index|
      if element > number && ascending?
        return index
      end

      if element < number && descending?
        return index
      end
    end

    length
  end

  def insert_sorted(number)
    insert(insert_index(number), number)
  end

  def ascending?
    first <= last
  end

  def descending?
    !ascending?
  end
end

Use it on a array as follows:

array = [2, 61, 12, 7, 98, 64]

ascending = array.sort
descending = array.sort.reverse

ascending.extend SortedInsert
descending.extend SortedInsert

number_to_insert = 3

puts "Descending: "

p number_to_insert
p descending
p descending.insert_sorted(number_to_insert)

puts "Ascending: "

p number_to_insert
p ascending
p ascending.insert_sorted(number_to_insert)

This will give:

Descending:
3
[98, 64, 61, 12, 7, 2]
[98, 64, 61, 12, 7, 3, 2]
Ascending:
3
[2, 7, 12, 61, 64, 98]
[2, 3, 7, 12, 61, 64, 98]

Notes:

1. The module defines a few methods that will be added to the specific Array object alone.
2. The new methods provides a sorted array (either ascending/descending) a method insert_sorted(number) which enables to insert the number at sorted position.
3. In case the position of insertion is required, there is a method for that too: insert_index(number), which will provide the index to which the number needs to be inserted so that the resultant array remains sorted.
4. Caveat: The module assumes the array being extended is sorted either as ascending or descending.

Answer 3

Here is the simplest way I can think of doing.

def find_insert_idx(ary, n)
  is_asc = (ary.sort == ary)
  if (is_asc)
    return ary.index { |i| i > n }
  else 
    return ary.index { |i| i < n }
  end
end

p find_insert_idx([1,5,7,11,51], 9)
#=> 3
p find_insert_idx([49,32,22,11,10,8,3,2], 9)
#=> 5