Efficient way of computing second min value

Question

Given a matrix, it's easy to compute the value and index of the min value:

A = rand(10);
[value, index] = min(A(:));

However I would also like to recover the second min value (idem for max).

I can of course take any of this two approaches:

1. Converting A to a vector and sorting it.

   PROS: I can then recover the second, third... n minimum value

   CONS: If A is large, sorting is expensive

2. Once the min location of A is located, I can replace this value by a large one (eg: Inf) and then run min again.

   PROS: Cheaper than sort

   CONS: I must modify my matrix (and save the modified value in an aux variable). Also re-running min is costly on a large matrix.

I'm wondering if there is a better solution:

When computing min the algorithm has to keep track of the min value found so far, until a new value has a lower value (then we update the value). If instead we keep track of the last n min values found so far will allow to recover the minimum n values.

I can implement this, but I'm wondering if it's the best approach or if it's already implemented.

Answer 1

I don't know in which case it would be less expensive than sorting, but an easy, but not so fast way would be to use the following code. I may be wrong, but I don't think you can get faster with build-in functions if you just want the first and the second min.

A = rand(10);
[firstMin, firstMinIndex] = min(A(:));
secondMin = min(A(A~=firstMin));
secondMinIndex = find(A==secondMin); % slow, but use only if you need the index

Here, you go through the matrix two times more, one for the boolean operation, and one for the second min.

After some testing on 2000x2000 and 4000x4000 random matrix, it seems that this code snipset is around 3.5 time faster than the sort function applied on the same matrix.

If you really need more efficiency, you'd have to write your own mex routine, with which you can theoretically get the two values in n+log n-2 comparison, as explained in the link provided by @luismendotomas.

Hope this help !