Menu
There are N values in the array, and one of them is the smallest value. How can I find the smallest value most efficiently?
207
We have to find the smallest/ minimum element in an array. The time complexity to solve this is linear O(N) and space compexity is O(1).
We traverse the array from i = 1 to n - 1 and compare each element with min and max. If (X[i] < min): We have found a value smaller than minimum till ith index. So update min with X[i] i.e min = X[i]. else If(X[i] > max): We have found a value greater than maximum till ith index.
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.
196
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
