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

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.