O algoritmo de busca ternária localiza um elemento em uma lista de números inteiros crescentes por sucessivas divisões da lista em três sublistas de tamanho igual (ou o mais próximo possivel de serem iguais) e restringe a busca na sublista apropriada. Especifique os passos deste algoritmo.
Passo 1
O enunciado pede a busca ternária em uma lista crescente de inteiros. O objetivo é, dado um vetor ordenado
e um valor
, localizar o índice onde
aparece (ou indicar que não existe), dividindo repetidamente o intervalo de busca em três partes.
Passo 2
Definimos dois ponteiros que delimitam o intervalo de procura:
e
. A cada iteração, enquanto
, vamos refinar esse intervalo. Se
, concluímos que
não está na lista.
Passo 3
Em cada iteração, calculamos os dois pontos de divisão que separam o intervalo
em três partes aproximadas iguais:
Passo 4
Comparamos
com
e
:
- Se
, retornamos . - Senão, se
, retornamos .
Passo 5
Se não encontramos
nos pivôs, escolhemos qual subintervalo ainda pode conter
e atualizamos
e
:
- Se
, buscamos em , atualizando . - Se
, buscamos em , atualizando . - Caso contrário
, buscamos em , definindo e .
Passo 6
Repetimos os passos 3 a 5 até encontrarmos
(retornando o índice) ou até
, quando devolvemos “não encontrado” (por exemplo,
).
Resposta
- Inicializar
, . - Enquanto
:
a. Calcular
b. Se
, retornar
; senão, se
, retornar
.
c. Se , ajustar
;
se , ajustar
;
caso contrário, ajustar e
.
3. Se sair do laço sem retornar, devolver “não encontrado” (por exemplo, ).
c. Se
se
caso contrário, ajustar
3. Se sair do laço sem retornar, devolver “não encontrado” (por exemplo,