Questão nº 42

Questão de Tecnologia da Informação · FCC TRT20 2024 (nº 42)

FCC2024Técnico Judiciário - Área Apoio Especializado - Especialidade Tecnologia da InformaçãoTecnologia da Informação

Considere o programa Java abaixo.

public class Verificar {

    public static int dados(int[] vetor, int inicio, int fim, int chave) {
        if (inicio > fim) {
            return -1;
        }
        int meio = (inicio + fim) / 2;
        if (vetor[meio] == chave) {
            return meio;
        }
        if (vetor[inicio] <= vetor[meio]) {
            if (chave >= vetor[inicio] && chave < vetor[meio]) {
                return dados(vetor, inicio, meio - 1, chave);
            } else {
                return dados(vetor, meio + 1, fim, chave);
            }
        } else {
            if (chave > vetor[meio] && chave <= vetor[fim]) {
                return dados(vetor, meio + 1, fim, chave);
            } else {
                return dados(vetor, inicio, meio - 1, chave);
            }
        }
    }

    public static void main(String[] args) {
        int[] vetor = {7, 8, 9, 1, 2, 3, 4, 5, 6};
        int resultado = dados(vetor, 0, 8, 5);
        System.out.println(resultado);
    }
}

Ao executar o programa, em condições ideais, será exibido na tela o valor

A7. (alternativa correta)
B6.
C8.
D3.
E5.

Resposta comentada

Gabarito Alternativa A

A busca binária é um algoritmo eficiente para encontrar um elemento em uma lista ordenada, dividindo-a repetidamente ao meio. No entanto, quando a lista está rotacionada (ou seja, um segmento inicial foi movido para o final, como {7, 8, 9, 1, 2, 3, 4, 5, 6} que é {1, 2, 3, 4, 5, 6, 7, 8, 9} rotacionado), a busca binária tradicional não funciona. Este algoritmo adaptado primeiro identifica qual metade do array (do segmento atual da busca) está ordenada e, em seguida, verifica se o elemento procurado (chave) está dentro do intervalo dessa metade ordenada. Se sim, a busca continua nessa metade; caso contrário, continua na outra metade, que pode estar rotacionada ou não.

(A) Correta: O valor 7 é o índice onde a chave 5 é encontrada no array vetor = {7, 8, 9, 1, 2, 3, 4, 5, 6}. O algoritmo realiza uma busca binária adaptada para arrays rotacionados.
1. Chamada 1: dados(vetor, 0, 8, 5). meio = 4 (vetor[4]=2). Como vetor[0] (7) é maior que vetor[4] (2), a primeira metade ([0...4]) está rotacionada e a segunda metade ([5...8], que é {3, 4, 5, 6}) está ordenada. A chave 5 está no intervalo (vetor[meio], vetor[fim]] (ou seja, (2, 6]), então a busca continua na segunda metade. Nova chamada: dados(vetor, 5, 8, 5).
2. Chamada 2: dados(vetor, 5, 8, 5). meio = 6 (vetor[6]=4). Como vetor[5] (3) é menor que vetor[6] (4), a primeira metade ([5...6], que é {3, 4}) está ordenada. A chave 5 não está no intervalo [vetor[inicio], vetor[meio]) (ou seja, [3, 4)), então a busca continua na segunda metade. Nova chamada: dados(vetor, 7, 8, 5).
3. Chamada 3: dados(vetor, 7, 8, 5). meio = 7 (vetor[7]=5). A chave 5 é igual a vetor[7], então o índice 7 é retornado.
(B) Incorreta: O valor 6 é o índice do elemento 4 no array, não da chave 5.
(C) Incorreta: O valor 8 é o índice do elemento 6 (o último elemento) no array, não da chave 5.
(D) Incorreta: O valor 3 é o índice do elemento 1 no array, não da chave 5.
(E) Incorreta: O valor 5 é a própria chave que está sendo procurada. O programa retorna o índice onde a chave é encontrada, não o valor da chave. Armadilha da banca: Uma confusão comum é retornar o valor da chave em vez do seu índice no array. Se o programa retornasse o valor da chave, a saída seria 5.

Fonte: FCC TRT20 2024 Técnico Judiciário - Área Apoio Especializado - Especialidade Tecnologia da Informação (Caderno Tipo 004). Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · FCC TRT20 2024 (nº 42)

Resposta comentada

Continue estudando