Efficient way for finding the min and max value in an array

Question

I want to find out the minimum and maximum value in an array of integers.

Which one of the following ways would be the more efficient?

1. Sort the array and then look at start and end to get the minimum and maximum.

2. Convert the array into a list using Arrays.asList() and then use the Collections.min() method.

The code where I want to use this is the following:

// Find missing number from an array of consecutive numbers arranged randomly
import java.util.Arrays;

public class MissingNumber {

    public static void main(String[] args) {

        int[] consecutiveRandomNos = { 3, 6, 5 };

        System.out.println(addNumbers(consecutiveRandomNos));
        System.out.println("The missing number is "
                        + (returnSum(consecutiveRandomNos) - addNumbers(consecutiveRandomNos)));
    }

    public static int addNumbers(int... numbers) {
        int result = 0;

        for (int number : numbers) {
            result += number;
        }

        return result;
    }

    public static int returnSum(int... nos) {

        Arrays.sort(nos);

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

        int min = nos[0];

        int total = 0;

        for (int i = min; i <= max; i++) {
            total += i;
        }

        return total;
    }
}

Answer 1

Sort is O(Nlog(N)) at best. You can find min and max trivially in O(n) just iterating over the array.

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i]
    if(array[i] > max)
       max = array[i]
}

Edit:

---

I noticed you pasted some extra code and that you actually want to find a missing number in an array of consecutive numbers. Rather than iterating all that much, there are mathematical summations that can help you here in O(1). In fact, you can solve the entire problem with a single for loop:

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int sum = 0;
for(int i=0; i<array.length; i++)
{
    if(array[i] < min)
       min = array[i];
    if(array[i] > max)
       max = array[i];
    sum += array[i];
}

return (max - min + 1)(max + min)/2 - sum;