Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am trying to find max value of an array, firstly i am shorting my array min to max after that i am using array[array.length-1] Is this logic efficient in large arrays?

public static int findMax(int[] array){

    Arrays.sort(array);

    int max = array[array.length-1];

    return max;
}//end method
share|improve this question
4  
The best find max algorithm on an array is an iteration with O(n). To get any better you need to be using a more efficient data structure than a straight array, like a self balancing binary tree or any of a number of other data structures which maintain a form of ordering for you. or you can always memoize the max. –  Jimmy Hoffa Nov 24 '12 at 21:15
    
May not be efficient for the computer, but in terms of SLOC and maintainability it's pretty good compared to the suggested alternates.... –  mattnz Nov 25 '12 at 2:57
add comment

2 Answers 2

up vote 1 down vote accepted

No it's not.

Arrays.sort(array);

That line alone has an O(nlogn) running time. It can result in as many iterations as n, where n is the number of elements in the array, multiplied by log base 2 of n.

It would be much faster to just iterate through the array once.

public static int findMax(int[] array) {
    int indexOfMax = 0;
    for (i=1; i < array.length; i++) {
        if (array[i] > array[indexOfMax] {
            indexOfMax = i;
    }
    return indexOfMax
}

That has a maximum running time as O(n).

share|improve this answer
    
-1 For gross misrepresentation of big O. First off, when discussing sorting algorithms, n is (usually) the number of comparisons, not the number of iterations through the array. Also, O(n log n) does not mean "as many as n times log_2 n", it means "For some constants c, b: the number is less than c * n * log_b n (for all n > some constant N_0)". It might as well be 5 * n * log_9(n) for n > 1000. –  delnan Nov 24 '12 at 23:19
1  
@delnan: I would not call his claim of O(n log n) running time to be a 'gross misrepresentation of big O'. This is exactly the sort of stuff big O is used for, and he cited it properly. –  whatsisname Nov 25 '12 at 6:49
    
Delnan is correct. However, my intention was to simplify things for the OP, who clearly has no CS education at all. And for an implementation of a library sort function, the base of the logarithm will invariably be 2. –  user16764 Nov 25 '12 at 8:50
    
@whatsisname He cited the right complexity but then interpreted it completely wrong. That doesn't help OP either, it just spreads misconceptions. I agree that my formulation is probably not useful for beginners. A more correct explanation that's even simpler is that it'll generally perform more work (than an O(n) algorithm) and is hence slower. –  delnan Nov 25 '12 at 12:19
1  
Delnan, honestly. Just edit the answer if you think you can improve it. –  user16764 Nov 25 '12 at 18:45
add comment

Cleaner implementation of the accepted answer:

public static int findMax(int[] array) {

    // TODO: Take appropriate action if the array is empty.

    int max_value = Integer.MIN_VALUE;

    for ( int value : array ) {
        if ( value > max_value ) {
            max_value = value;
        }
    }

    return max_value;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.