Is there a better way to find the location of a minimum element in an Array?

Question

Right now I have

def min(array,starting,ending)
  minimum = starting
  for i in starting+1 ..ending
    if array[i]<array[minimum]
      minimum = i
    end    
  end

return minimum
end

Is there a better "implementation" in Ruby? This one still looks c-ish. Thanks.

Answer 1

This is the standard algorithm for finding the minimum element in an array, it can be better by having the array already be sorted before this function is called.

Otherwise I can't find a more efficient way of doing this. Specifically, linear time in big O notation is the best we can do.

Answer 2

If this isn't simply an academic question, why not just use Ruby's native sort method? It's implemented using a quicksort algorithm, and is considered to be pretty fast.

a = [3, 4, 5, 1, 7, 5]
a.sort![0] # => 1

Answer 3

Basically that's the best you can do, though you can write it a bit more succinctly:

def minval(arr)
    arr.inject {|acc,x| (acc && acc < x ? acc : x)}
end

Answer 4

If you want to find the index of the minimal element, you can use Enumerable#enum_for to get an array of items-index pairs, and find the minimum of those with Enumerable#min (which will also be the minimum of the original array).

% irb
irb> require 'enumerator'
#=> true
irb> array = %w{ the quick brown fox jumped over the lazy dog }
#=> ["the", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"]
irb> array.enum_for(:each_with_index).min
#=> ["brown", 2]

If you want to bound it to specific array indices:

irb> start = 3
#=> 3
irb> stop = 7
#=> 7
irb> array[start..stop].enum_for(:each_with_index).min
#=> ["fox", 0]
irb> array[start..stop].enum_for(:each_with_index).min.last + start
#=> 3