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 \text{A}[0\dots n-1] e um valor x, localizar o índice onde x 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: \ell = 0 e r = n-1. A cada iteração, enquanto \ell \le r, vamos refinar esse intervalo. Se \ell>r, concluímos que x não está na lista.

Passo 3

Em cada iteração, calculamos os dois pontos de divisão que separam o intervalo \text{A}[\ell\dots r] em três partes aproximadas iguais:
m_1 = \ell + \left\lfloor\frac{r - \ell}{3}\right\rfloor
m_2 = r - \left\lfloor\frac{r - \ell}{3}\right\rfloor

Passo 4

Comparamos x com \text{A}[m_1] e \text{A}[m_2]:
  • Se \text{A}[m_1] = x, retornamos m_1.
  • Senão, se \text{A}[m_2] = x, retornamos m_2.

Passo 5

Se não encontramos x nos pivôs, escolhemos qual subintervalo ainda pode conter x e atualizamos \ell e r:
  • Se x < \text{A}[m_1], buscamos em \text{A}[\ell\dots m_1-1], atualizando r = m_1 - 1.
  • Se x > \text{A}[m_2], buscamos em \text{A}[m_2+1\dots r], atualizando \ell = m_2 + 1.
  • Caso contrário \text{A}[m_1] < x < \text{A}[m_2], buscamos em \text{A}[m_1+1\dots m_2-1], definindo \ell = m_1 + 1 e r = m_2 - 1.

Passo 6

Repetimos os passos 3 a 5 até encontrarmos x (retornando o índice) ou até \ell > r, quando devolvemos “não encontrado” (por exemplo, -1).

Resposta

  1. Inicializar \ell = 0, r = n-1.
  2. Enquanto \ell \le r:
    a. Calcular
m_1 = \ell + \Big\lfloor\frac{r - \ell}{3}\Big\rfloor,\quad m_2 = r - \Big\lfloor\frac{r - \ell}{3}\Big\rfloor.
b. Se \text{A}[m_1]=x, retornar m_1; senão, se \text{A}[m_2]=x, retornar m_2.
c. Se x<\text{A}[m_1], ajustar r = m_1-1;
se x>\text{A}[m_2], ajustar \ell = m_2+1;
caso contrário, ajustar \ell = m_1+1 e r = m_2-1.
3. Se sair do laço sem retornar, devolver “não encontrado” (por exemplo, -1).

Exercícios de Livros Relacionados