Finding smallest value in an array most efficiently

Question

There are N values in the array, and one of them is the smallest value. How can I find the smallest value most efficiently?

Answer 1

You need too loop through the array, remembering the smallest value you've seen so far. Like this:

int smallest = INT_MAX;
for (int i = 0; i < array_length; i++) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}

Answer 2

If they are unsorted, you can't do much but look at each one, which is O(N), and when you're done you'll know the minimum.

---

Pseudo-code:

small = <biggest value> // such as std::numerical_limits<int>::max
for each element in array:
    if (element < small)
        small = element

A better way reminded by Ben to me was to just initialize small with the first element:

small = element[0]
for each element in array, starting from 1 (not 0):
    if (element < small)
        small = element

The above is wrapped in the algorithm header as std::min_element.

---

If you can keep your array sorted as items are added, then finding it will be O(1), since you can keep the smallest at front.

That's as good as it gets with arrays.

Answer 3

The stl contains a bunch of methods that should be used dependent to the problem.

std::find
std::find_if
std::count
std::find
std::binary_search
std::equal_range
std::lower_bound
std::upper_bound

Now it contains on your data what algorithm to use. This Artikel contains a perfect table to help choosing the right algorithm.

---

In the special case where min max should be determined and you are using std::vector or ???* array

std::min_element
std::max_element

can be used.

Answer 4

An O(1) sollution might be to just guess: The smallest number in your array will often be 0. 0 crops up everywhere. Given that you are only looking at unsigned numbers. But even then: 0 is good enough. Also, looking through all elements for the smallest number is a real pain. Why not just use 0? It could actually be the correct result!

If the interviewer/your teacher doesn't like that answer, try 1, 2 or 3. They also end up being in most homework/interview-scenario numeric arrays...

On a more serious side: How often will you need to perform this operation on the array? Because the sollutions above are all O(n). If you want to do that m times to a list you will be adding new elements to all the time, why not pay some time up front and create a heap? Then finding the smallest element can really be done in O(1), without resulting to cheating.

Answer 5

If finding the minimum is a one time thing, just iterate through the list and find the minimum.

If finding the minimum is a very common thing and you only need to operate on the minimum, use a Heap data structure.

A heap will be faster than doing a sort on the list but the tradeoff is you can only find the minimum.

Answer 6

If you're developing some kind of your own array abstraction, you can get O(1) if you store smallest added value in additional attribute and compare it every time a new item is put into array.

It should look something like this:

class MyArray
{
public:
    MyArray() : m_minValue(INT_MAX) {}

    void add(int newValue)
    {
        if (newValue < m_minValue) m_minValue = newValue;
        list.push_back( newValue );
    }

    int min()
    {
        return m_minValue;
    }

private:
    int m_minValue;
    std::list m_list;
}

Answer 7

Note this fails for array size of zero.

#include <iostream.h>

double min(double *values, int size)
{
    double min = values[0];
    for (int i = 1; i < size; i++)
        if (values[i] < min)
            min = values[i];
    return min;
}

void main()
{
    double values[] = { 5, 4, 3, 2, 1, 6, 7, 8, 9, -53 };
    cout << min(values, sizeof(values) / sizeof(double));
}

As others have said, it's O(n) absent any knowledge about ordering of the values, so you just iterate through them.

Answer 8

Richie's answer is close. It depends upon the language. Here is a good solution for java:

int smallest =  Integer.MAX_VALUE;
int array[]; // Assume it is filled.
int array_length = array.length;
for (int i = array_length - 1; i >= 0; i--) {
    if (array[i] < smallest) {
        smallest = array[i];
    }
}

I go through the array in reverse order, because comparing "i" to "array_length" in the loop comparison requires a fetch and a comparison (two operations), whereas comparing "i" to "0" is a single JVM bytecode operation. If the work being done in the loop is negligible, then the loop comparison consumes a sizable fraction of the time.

Of course, others pointed out that encapsulating the array and controlling inserts will help. If getting the minimum was ALL you needed, keeping the list in sorted order is not necessary. Just keep an instance variable that holds the smallest inserted so far, and compare it to each value as it is added to the array. (Of course, this fails if you remove elements. In that case, if you remove the current lowest value, you need to do a scan of the entire array to find the new lowest value.)