Valor Máximo e Valor Mínimo de um Vetor

Como o título sugere, o intuito desta postagem é apresentar os algoritmos que localizam o valor máximo e o valor mínimo de um vetor (ou array), além da implementação dos mesmos em Java.

Valor Máximo

A ideia básica é supor que o primeiro elemento do vetor seja o maior e compará-lo com os demais elementos. Se algum elemento maior for encontrado, então continuamos as comparações com o novo maior elemento. O algoritmo encerra quando o final do vetor é alcançado.

Ao localizar um 'novo máximo', não precisamos voltar ao início do vetor para reiniciar as comparações, bastando continuar a partir do índice onde o 'novo máximo' está.

O algoritmo (em pseudocódigo) é dado por (o primeiro índice é zero):

max(A)
      n ← A.tamanho
      max ← A[0] //supõe-se que o primeiro é o maior
      para i = 1 até n - 1
            se (max < A[i]) //novo máximo encontrado
                  max ← A[i]
            fim_se
      fim_para
      retorne max //retorna o valor máximo
fim

O melhor caso do algoritmo ocorre quando o primeiro valor é o máximo, pois apenas a primeira atribuição é realizada (max ← A[0]). Por outro lado, o pior caso ocorre quando o vetor está ordenado em ordem crescente, pois a atribuição max ← A[i] sempre será realizada, isto é, a condição max < A[i] sempre será verdadeira.

Entretanto, em ambos os casos, a complexidade no tempo é O(n). O caso médio também é O(n).

Código em Java

A seguir, apresento o algoritmo codificado em Java. Além do método que retorna o maior valor, também há um método que retorna o índice do maior valor (a lógica é a mesma).

//Code by Henrique Felipe (GitHub: HenriqueIni)
public class MaxValueArray {
    //Return the maximum value of an array
    public static int maxValue(int[] a){
        int max = a[0]; //the first element is the supposed max
        for(int i = 1; i < a.length; i++){
            //a value greater than max was found
            if(max < a[i]){
                max = a[i]; //replace the max value
            }
        }
        return max; //return the max value
    }
    //Return the index of the maximum value of an array
    public static int maxValueIndex(int[] a){
        int maxIndex = 0; //the first element is the supposed max
        int maxValue = a[0];
        for(int i = 1; i < a.length; i++){
            //a value greater than max was found
            if(maxValue < a[i]){
                maxValue = a[i]; //replace the max value
                maxIndex = i; //replace the max index
            }
        }
        return maxIndex; //return the max index
    }
    //tests
    public static void main(String[] args){
        int[] a = {-1, 2, -3, -4, 5, 8, 10, 20, 80, -1000, 9};
        System.out.println("Maximum value = " + maxValue(a));
        System.out.println("Maximum value index = " + maxValueIndex(a));
    }
}

Valor Mínimo

Utilizaremos a mesma lógica do valor máximo para obter o valor mínimo de um vetor: vamos supor que o primeiro elemento é o menor e comparamos com os demais elementos. Como o algoritmo é quase o mesmo, então não vou prolongar o texto:

min(A)
      n ← A.tamanho
      min ← A[0] //supõe-se que o primeiro é o menor
      para i = 1 até n - 1
            se (min > A[i]) //novo mínimo encontrado
                  min ← A[i]
            fim_se
      fim_para
      retorne min //retorna o valor mínimo
fim

A complexidade do algoritmo também é O(n) nos três casos (melhor, médio, pior).

Código em Java

A seguir, apresento o algoritmo codificado em Java. Além do método que retorna o menor valor, também há um método que retorna o índice do menor valor (a lógica é a mesma).

//Code by Henrique Felipe (GitHub: HenriqueIni)
public class MinValueArray {
    //Return the minimum value of an array
    public static int minValue(int[] a){
        int min = a[0]; //the first element is the supposed min
        for(int i = 1; i < a.length; i++){
            //a value less than min was found
            if(min > a[i]){
                min = a[i]; //replace the min value
            }
        }
        return min; //return the min value
    }
    //Return the index of the minimum value of an array
    public static int minValueIndex(int[] a){
        int minIndex = 0; //the first element is the supposed min
        int minValue = a[0];
        for(int i = 1; i < a.length; i++){
            //a value less than min was found
            if(minValue > a[i]){
                minValue = a[i]; //replace the min value
                minIndex = i; //replace the min index
            }
        }
        return minIndex; //return the min index
    }
    //tests
    public static void main(String[] args){
        int[] a = {-1, 2, -3, -4, 5, 8, 10, 20, 80, -1000, 9};
        System.out.println("Minimum value = " + minValue(a));
        System.out.println("Minimum value index = " + minValueIndex(a));
    }
}