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
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.
Passo 1
Estamos com um vetor desordenado
de tamanho
e queremos achar a primeira ocorrência de um elemento
usando recursão e uma divisão “ao meio” inspirada na busca binária. O que vamos precisar:
- Definir parâmetros de recursão
. - Ter um caso base para quando o subvetor estiver vazio.
- Calcular o índice do meio
. - Seguir a dica: se
, 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
.
Caso base:
se , o subvetor está vazio, então não encontramos
e retornamos
.
Caso base:
se
Passo 3
Calculamos
Se
, isso nos garante que
é uma ocorrência de
. Mas ainda pode haver uma primeira ocorrência mais à esquerda, então:
. chamamos recursivamente
;
. se o resultado for
, retornamos esse resultado (é uma ocorrência anterior);
. senão retornamos
.
Passo 4
Se
, então
pode estar tanto no lado esquerdo quanto no lado direito (ou não existir).
. chamamos
;
. chamamos
;
. se ambos
, retornamos
;
. se só um dos dois for
, retornamos esse;
. caso contrário, retornamos
.
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\)