Insert a number into an ordered array

Question

I have an array of numbers sorted in ascending or descending order, and I want to find the index into which to insert the number while maintaining the order of the array. If the array is [1, 5, 7, 11, 51] and the insert number is 9 , I would expect 3 so that I can make [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 expect 5 so that I can do [49, 32, 22, 11, 10, 8, 3, 2].insert(5, 9)

What is the best / cleanest way to find the index where you need to insert 9 into either of these two arrays while maintaining the array sort?

I wrote this code that works, but it is 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 is not bad, but it has two problems:

• It sorts the entire array to determine if it will be up or down. It's stupid when all you have to do is Find one item that does not match the previous one. compare the first and last elements to determine this. it O (n) O (1) in the worst case, instead of O (n log n).

• It uses Array#index when it should use bsearch . We can do a binary search instead of iterating over the entire array, because it is sorted. This is O (log n) in the worst case, instead of O (n).

It seemed to me that it would be easier to split it into two methods, but you, of course, could 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 

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

Answer 2

Here is the easiest way I can come up with.

 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 

Answer 3

This is not a very good way, but it may be cleaner since you can use the insert_sorted(number) method in any ascending or descending array without worrying about the index that it will place:

 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 in an 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

• The module defines several methods that will be added only to a specific Array object.
• The new methods provide a sorted array (or up / down) of the insert_sorted(number) method, which allows you to insert a number into a sorted position.
• If an insertion position is required, there is also a method for this: insert_index(number) , which will provide an index whose number must be inserted so that the resulting array remains sorted.
• Caution: the module assumes that the extended array is sorted either ascending or descending.