Desenvolva algoritmos recursivos para cada um dos seguintes problemas:
Busca sequencial em um vetor desordenado que retorna a posição da primeira ocorrência de um elemento procurado usando uma estratégia similar a da busca binária.
Dica: Se não é o elemento do meio, procure dos dois lados e retorne o menor dos índices encontrados. Se for o elemento do meio, continue a busca apenas do lado esquerdo, retornando a posição de lá se encontrar e o meio senão encontrar

Passo 1

Estamos com um vetor desordenado v de tamanho n e queremos achar a primeira ocorrência de um elemento x usando recursão e uma divisão “ao meio” inspirada na busca binária. O que vamos precisar:
  • Definir parâmetros de recursão (\text{low},\text{high}).
  • Ter um caso base para quando o subvetor estiver vazio.
  • Calcular o índice do meio \displaystyle \text{mid} = \left\lfloor \frac{\text{low} + \text{high}}{2} \right\rfloor.
  • Seguir a dica: se v[\text{mid}]=x, explorar apenas o lado esquerdo para ver se há uma ocorrência anterior; se não for igual, buscar ambos os lados e pegar o menor índice retornado.

Passo 2

Definimos a função recursiva com assinatura
\text{buscaRec}(v,\text{low},\text{high},x).
Caso base:
se \text{low} > \text{high}, o subvetor está vazio, então não encontramos x e retornamos -1.

Passo 3

Calculamos
\text{mid} = \left\lfloor \frac{\text{low} + \text{high}}{2} \right\rfloor.
Se v[\text{mid}] = x, isso nos garante que \text{mid} é uma ocorrência de x. Mas ainda pode haver uma primeira ocorrência mais à esquerda, então:
1. chamamos recursivamente \text{buscaRec}(v,\text{low},\text{mid}-1,x);
2. se o resultado for \neq -1, retornamos esse resultado (é uma ocorrência anterior);
3. senão retornamos \text{mid}.

Passo 4

Se v[\text{mid}] \neq x, então x pode estar tanto no lado esquerdo quanto no lado direito (ou não existir).
1. chamamos \text{posEsq} = \text{buscaRec}(v,\text{low},\text{mid}-1,x);
2. chamamos \text{posDir} = \text{buscaRec}(v,\text{mid}+1,\text{high},x);
3. se ambos \neq -1, retornamos \min(\text{posEsq},\text{posDir});
4. se só um dos dois for \neq -1, retornamos esse;
5. caso contrário, retornamos -1.

Resposta

função buscaRec(vetor \(v\), inteiro \(low\), inteiro \(high\), elemento \(x\))
    // Caso base: subvetor vazio
    se \(low > high\) então
        retorne \(-1\)
    // calcula o meio
    \(mid \leftarrow \frac{low + high}{2}\)
    // se achou no meio, tenta achar à esquerda antes de aceitar mid
    se \(v[mid] = x\) então
        \(posEsq \leftarrow buscaRec(v, low, mid - 1, x)\)
        se \(posEsq \neq -1\) então
            retorne \(posEsq\)
        senão
            retorne \(mid\)
    senão
        // busca em ambos os lados
        \(posEsq \leftarrow buscaRec(v, low, mid - 1, x)\)
        \(posDir \leftarrow buscaRec(v, mid + 1, high, x)\)
        se \(posEsq \neq -1\) e \(posDir \neq -1\) então
            retorne mínimo(\(posEsq\), \(posDir\))
        senão se \(posEsq \neq -1\) então
            retorne \(posEsq\)
        senão
            retorne \(posDir\)

Exercícios relacionados