- Nunca entendo o propósito de escrever um programa interativo cuja interatividade possa ser evitada. E é o caso aqui. Porque ler o vetor a cada teste? Ele tem que estar ordenado e nada tem a ver com o problema em si da tal busca ternária. Isso quer dizer que além de ter que digitar o vetor a cada teste tem que ficar atento para manter a ordem.
- Porque alocar o vetor dinamicamente ao invés de testar com um tamanho qualquer?
- porque nunca testar o retorno de
scanf()
se não faz sentido seguir se não leu nada?
- porque não liberar a memória ao final mesmo sendo um programa simples de teste?
int buscaTernaria(int n, int *v, int num)
Porque retornar -1
ou 1
? Não seria muito mais conveniente retornar a posição do vetor onde está o elemento ou um valor negativo se o elemento não fosse encontrado?
Acho que o código como postado seria bem simplificado se tivesse um_terco
e dois_tercos
computados para simplificar o loop.
De todo modo vou deixar um exemplo que funciona para busca ternária ou binária ou n-aria
para N
segmentos e que pode usar para comparar.
Eis o protótipo:
typedef long long int LLI;
typedef unsigned long long int ULL;
ULL busca_N_aria(LLI alvo, LLI* vetor, size_t inicio, size_t final);
Deixei esses typedef
para poder usar matrizes muito grandes e não ter que digitar toda hora esses tipos compridos. E usei size_t
porque são índices afinal e não podem ser negativos.
const int n_seg = 3; // 3 para busca ternaria
No exemplo essa linha define a busca ternária. Um 2
seria para a busca binária normal e um 8 faria a busca em 8 segmentos por vez, por exemplo.
Claro que poderia ser um argumento.
o código para a função
// busca 'alvo' no vetor 'vec' entre os indices
// 'inicio' e 'final'. O vetor e suposto ordenado.
ULL busca_N_aria(LLI alvo, LLI* vec, size_t inicio, size_t final)
{
const int n_seg = 3; // 3 para busca ternaria
if (vec[inicio] > alvo) return -1; // nao tem mesmo
if (vec[inicio] == alvo) return inicio;
if (vec[final] < alvo) return -1; // nao tem mesmo
if (vec[final] == alvo) return final;
// define o tamanho de cada segmento
size_t seg = (final - inicio - 2) / n_seg;
if (seg <= 0) seg = 1;
size_t ini = inicio + 1;
size_t fim = ini + seg;
while (1)
{
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] == alvo) return fim; // era o ultimo
// esta no meio desse segmento entao
if (vec[fim] > alvo) return busca_N_aria(alvo, vec, ini+1, fim-1);
ini += seg; // reajusta
fim += seg;
if ((final - fim) < seg) fim = final;
}
return -1;
}
outra maneira simples 2-aria 3-aria ou N-aria
ULL busca_N_aria(
LLI alvo, LLI* vec, size_t inicio, size_t final)
{
const int n_seg = 3; // 3 para busca ternaria
if (vec[inicio] > alvo) return -1; // nao tem mesmo
if (vec[inicio] == alvo) return inicio;
if (vec[final] < alvo) return -1; // nao tem mesmo
if (vec[final] == alvo) return final;
size_t ini = inicio + 1; // busca entre
size_t fim = final - 1; // os limites
while (1)
{
size_t seg = (fim - ini) / n_seg;
if (seg <= 0) seg = 1;
fim = ini + seg;
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] == alvo) return fim; // era o ultimo
if (vec[fim] > alvo)
{ // busca nesse segmento
ini += 1;
fim -= 1;
}
else
{ // segue adiante
ini += seg; // reajusta
fim += seg;
if ((final - fim) < seg) fim = final;
}
}
return -1; // nao vai passar aqui
}
Esta função faz a busca binária ou ternária ou centenária bastando mudar a constante n_seg
como a anterior
Usando a mesma alteração para corrigir o código original
int buscaTernaria(int alvo, int* vec, int num)
{
int ini = 0; // busca entre
int final = num - 1; // os limites
int fim = final;
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] < alvo) return -1; // nao tem mesmo
if (vec[fim] == alvo) return fim;
while (1)
{
int terco = (fim-ini) / 3;
if (terco <= 0) terco = 1;
fim = ini + terco;
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] == alvo) return fim; // era o ultimo
if (vec[fim] > alvo)
{ // busca nesse segmento
ini += 1;
fim -= 1;
}
else
{ // segue adiante: proximo terco
ini += terco; // reajusta
fim += terco; // limites
if ((final - fim) < terco) fim = final;
}
}
return -1;
}
- mudei os nomes de algumas variáveis
- no loop achei mais simples a função não sair do
while()
e simplesmente retornar ao concluir a busca
- o último
if
corrige o problema do tamanho dos segmentos ao invés de usar contas e float
um programa de teste
O programa abaixo não é interativo e faz o simples:
- aloca um vetor de tamanho
N
e preenche com valores pares ordenados.
- num loop chama a função de busca procurando por todos os valores possíveis desde um menor até um maior que todos os elementos do vetor
- como só tem valores pares não vai achar nenhum dos ímpares e como procura por todos valores possíveis deve achar todos os pares, e assim testa tudo sem stress
- como é chato ficar procurando o programa retorna o índice do valor encontrado no vetor e o valor na posição, e assim responde a pergunta óbvia: "o valor é esse mesmo?"
saída do teste para um vetor de 10 elementos
10 valores, v[0] = 0, v[9] = 18
==> nao encontrou -2 no vetor
==> nao encontrou -1 no vetor
==> busca por 0 retornou 0, v[0] = 0
==> nao encontrou 1 no vetor
==> busca por 2 retornou 1, v[1] = 2
==> nao encontrou 3 no vetor
==> busca por 4 retornou 2, v[2] = 4
==> nao encontrou 5 no vetor
==> busca por 6 retornou 3, v[3] = 6
==> nao encontrou 7 no vetor
==> busca por 8 retornou 4, v[4] = 8
==> nao encontrou 9 no vetor
==> busca por 10 retornou 5, v[5] = 10
==> nao encontrou 11 no vetor
==> busca por 12 retornou 6, v[6] = 12
==> nao encontrou 13 no vetor
==> busca por 14 retornou 7, v[7] = 14
==> nao encontrou 15 no vetor
==> busca por 16 retornou 8, v[8] = 16
==> nao encontrou 17 no vetor
==> busca por 18 retornou 9, v[9] = 18
==> nao encontrou 19 no vetor
==> nao encontrou 20 no vetor
O programa de teste
int main(void)
{
size_t tamanho = 10;
LLI* vetor = (ULL*)malloc(tamanho * sizeof(ULL));
for (size_t i = 0; i < tamanho; i += 1)
*(i + vetor) = (int)(i + i);
// o vetor tem apenas valores pares
// para ficar facil de testar:
// esta ordenado de 0 ao final e nao
// tem nenhum valor impar
printf("\n %llu valores, v[%llu] = %lli, v[%llu] = %lli\n\n",
tamanho,
(size_t)0, *vetor,
tamanho - 1,
*(vetor + tamanho - 1));
for (LLI alvo = -2; alvo <= (LLI)(tamanho + tamanho);
alvo += 1)
{
LLI res = busca_N_aria(alvo, vetor, 0, tamanho - 1);
if (res >= 0)
printf(
"==> busca por %lli retornou"
" %lli, v[%llu] = %lli\n",
alvo, res, res, vetor[res]);
else
printf(
"==> nao encontrou %lli no vetor\n", alvo);
};
free(vetor);
vetor = NULL;
return 0;
}
o codigo completo
#include <stdio.h>
#include <stdlib.h>
typedef long long int LLI;
typedef unsigned long long int ULL;
ULL busca_N_aria(LLI, LLI*, size_t, size_t);
int main(void)
{
size_t tamanho = 10;
LLI* vetor = (ULL*)malloc(tamanho * sizeof(ULL));
for (size_t i = 0; i < tamanho; i += 1)
*(i + vetor) = (int)(i + i);
// o vetor tem apenas valores pares
// para ficar facil de testar:
// esta ordenado de 0 ao final e nao
// tem nenhum valor impar
//clang-format-off
printf("\n %llu valores, v[%llu] = %lli, v[%llu] = %lli\n\n",
tamanho,
(size_t)0, *vetor,
tamanho - 1,
*(vetor + tamanho - 1));
//clang-format-on
for (LLI alvo = -2; alvo <= (LLI)(tamanho + tamanho);
alvo += 1)
{
LLI res = busca_N_aria(alvo, vetor, 0, tamanho - 1);
if (res >= 0)
printf(
"==> busca por %lli retornou"
" %lli, v[%llu] = %lli\n",
alvo, res, res, vetor[res]);
else
printf(
"==> nao encontrou %lli no vetor\n", alvo);
};
free(vetor);
vetor = NULL;
return 0;
}
// busca 'alvo' no vetor 'vec' entre os indices
// 'inicio' e 'final'. O vetor e suposto ordenado.
ULL busca_N_aria(LLI alvo, LLI* vec, size_t inicio, size_t final)
{
const int n_seg = 3; // 3 para busca ternaria
if (vec[inicio] > alvo) return -1; // nao tem mesmo
if (vec[inicio] == alvo) return inicio;
if (vec[final] < alvo) return -1; // nao tem mesmo
if (vec[final] == alvo) return final;
// define o tamanho de cada segmento
size_t seg = (final - inicio - 2) / n_seg;
if (seg <= 0) seg = 1;
size_t ini = inicio + 1;
size_t fim = ini + seg;
while (1)
{
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] == alvo) return fim; // era o ultimo
// esta no meio desse segmento entao
if (vec[fim] > alvo) return busca_N_aria(alvo, vec, ini+1, fim-1);
ini += seg; // reajusta
fim += seg;
if ((final - fim) < seg) fim = final;
}
return -1;
}
um teste da função original com a correção
#include <stdio.h>
#include <stdlib.h>
int buscaTernaria(int,int*,int);
int main(void)
{
int tamanho = 11;
int* vetor = (int*)malloc(tamanho * sizeof(int));
for (int i = 0; i < tamanho; i += 1)
*(i + vetor) = (int)(i + i);
printf(
"\n %d valores, v[%d] = %d, v[%d] = "
"%d\n\n",
tamanho, 0, *vetor, tamanho - 1,
*(vetor + tamanho - 1));
for (int alvo = -2; alvo <= (int)(tamanho + tamanho);
alvo += 1)
{
int res = buscaTernaria(alvo, vetor, tamanho);
if (res >= 0)
printf("==> busca por %d retornou"
" %d, v[%d] = %d\n",
alvo, res, res, vetor[res]);
else
printf(
"==> nao encontrou %d no vetor\n", alvo);
};
free(vetor);
vetor = NULL;
return 0;
}
int buscaTernaria(int alvo, int* vec, int num)
{
int ini = 0; // busca entre
int final = num - 1; // os limites
int fim = final;
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] < alvo) return -1; // nao tem mesmo
if (vec[fim] == alvo) return fim;
while (1)
{
int terco = (fim-ini) / 3;
if (terco <= 0) terco = 1;
fim = ini + terco;
if (vec[ini] > alvo) return -1; // nao tem mesmo
if (vec[ini] == alvo) return ini;
if (vec[fim] == alvo) return fim; // era o ultimo
if (vec[fim] > alvo)
{ // busca nesse segmento
ini += 1;
fim -= 1;
}
else
{ // segue adiante: proximo terco
ini += terco; // reajusta
fim += terco; // limites
if ((final - fim) < terco) fim = final;
}
}
return -1;
}
float
. Uma única linha e pode estender o último segmento para compensar o arredontamento da disão por inteiro.if ((final - fim) < seg) fim = final;
ondefinal
é o último índice válido e 'fim' é o últomo índice do segmento