Smallest array element in Java

Question

I have an Integer array, value[]. It may be of any length.

I need to find the smallest number. I am working on a problem in interview street. I am getting an error as my Time Exceeded. I need to increase the speed of computing the smallest value, as iterating gets worse.

I am interested in using Java collections or anything else, so anyone give some suggestions to improve the code.

int mini=value[0];
for (int i = 1; i < noinps; i++) {
    if(mini>value[i]) {
        mini=value[i];
    }
}
System.out.println(mini);

Answer 1

There isn't a better algorithm for finding the minimum or maximum element in an array. You have to look at every element. Maybe you lose time somewhere else - for example reading the input.

Answer 2

The algorithm seems fine for finding the minimum value of an array. If nothing is known about the possible elements contained in the arraym, you need to inspect each element, so your performance is linear (directly proportional to the number on elments in the array).

If the elements are fully ordered ordered, you can just look up the first (or last, dependng or ordering) element (constant time performance)

If the elements are semi-ordered (e.g. heap structure), you could find it via a binary search-like technique (log(n) performance)

If the elements are unordered, but you know they cannot be less than a certain value, you can stop the search if you find the smallest possible value.

So back to the timeout problem: if the elements are unordered and there are no other restrictions on them, your algorithm is fine, so the timeout must come form some other part of the program (e.g. you are trying to read from the console, but the data is in a file)