Questões de Algoritmos de Busca (Algoritmos e Estrutura de Dados)

Em uma agência bancária, as filas de atendimento são ordenadas da esquerda para a direita, e o gerente dessa agência percebeu a presença equivocada de um idoso, com a senha 52, na fila de atendimento não preferencial. Visando a sanar o equívoco, o gerente resolveu que, na primeira oportunidade, faria uma busca no sistema para saber se a senha 52 ainda estava ativa, indicando a presença do idoso na fila de atendimento não preferencial. Em caso de resposta positiva, procuraria o cliente para trocar sua senha por outra de atendimento preferencial; se não, apenas registraria o fato para posterior discussão no grupo de qualidade de atendimento.
Considerando o uso de um algoritmo de busca sequencial otimizado, partindo da esquerda para a direita, e as sequências hipotéticas das senhas da fila de atendimento não preferencial e suas regras de ordenação, segundo as quais quem está à esquerda é atendido antes de quem está à direita, o menor número de comparações para o gerente conhecer o resultado de sua busca ocorre em

Desejam-se realizar buscas nas seguintes coleções de dados, representadas na linguagem Java:
I - Um array de 1.000 números inteiros ordenados de forma decrescente; II - Uma lista encadeada desordenada e alocada dinamicamente, cujos 1.000 nós contêm strings (uma string por nó); III - Uma lista encadeada, alocada dinamicamente, cujos 1.000 nós contêm números decimais (um número double por nó) ordenados de forma ascendente.
Levando-se em consideração a exequibilidade e a eficiência, quais métodos de busca devem ser empregados, respectivamente, em cada um dos três casos acima?

Considere uma lista ordenada, contendo 20 chaves únicas, na qual seja realizada uma busca binária. Assinale o número máximo de acessos necessários para encontrar uma determinada chave.

O seguinte trecho de código, implementado em Java, realiza a busca por uma chave x em um vetor de inteiros A, que encontra-se ordenado crescentemente. Os parâmetros p e r delimitam o subvetor A[p..r].
private static int busca(int[] A, int p, int r, int x) { if (p > r) return -1; else{ int q = (p + r) / 2; if(A[q] == x) return q; else if(A[q] > x) return busca(A, p, q-1, x); else return busca(A, q+1, r, x); } }
O trecho de código apresentado implementa uma busca