-3

Tentei utilizar várias variações desse código com a menor complexidade que consegui pensar, mas nenhum deu certo para todos os números procurados. O vetor inserido já é ordenado. Já tentei também resolver analisando os números truncados para float quando o decimal da divisão de "terco" é maior ou igual a 0.5, mas não resolveu.

#include <stdio.h>
#include <stdlib.h>

int buscaTernaria(int n, int *v, int num);

int main(){
    int n;
    printf("Entre tamanho do vetor: ");
    scanf("%d", &n);

    int* v = malloc(n * sizeof(int));

    printf("Entre os elementos do vetor: ");

    int i = 0;
    while(i < n){
        scanf("%d", &v[i]);
        i++;
    }

    int num;
    printf("Entre número que deseja encontrar: ");
    scanf("%d", &num);

    int search = buscaTernaria(n, v, num);

    if(search != -1) printf("O número %d é elemento do vetor", num);
    else printf("Número não encontrado como elemento do vetor");
}

int buscaTernaria(int n, int *v, int num){
    int i = 0;
    int f = n-1;
    
    while(i < f){
        int terco; 
        if((float)(i+f)/3 - (i+f)/3 < 0.5) terco = (i+f)/3; 
        else terco = (i+f)/3 + 1;
        
        if(v[terco] < num) i = terco;
        else if(v[f - terco] < num) i = f - terco;
        
        if(v[f - terco] > num) f = f - terco;   
        else if(v[terco] > num) f = terco;
        
        printf("i:%d f:%d\n", i, f);
        
        int m = (i+f)/2;
        if(v[m] == num || v[m] == num+1) return 1;
    }

    return -1;
}
2
  • Leu o código que eu mostrei? Não precisa ficar com a busca ternária: todos os segmentos são similares e o número deles não faz diferença. Não precisa usar float. Uma única linha e pode estender o último segmento para compensar o arredontamento da disão por inteiro.
    – arfneto
    Commented 11/09/2022 às 20:08
  • Essa linha if ((final - fim) < seg) fim = final; onde final é o último índice válido e 'fim' é o últomo índice do segmento
    – arfneto
    Commented 11/09/2022 às 20:10

2 Respostas 2

2

Tem alguns problemas com o seu algoritmo:

  • seu algoritmo não imprime a posição do elemento pesquisado no vetor de entrada
    if(search != -1) printf("O número %d é elemento do vetor", num);
  • seu algoritmo apenas imprime -1 se o elemento pesquisado não for encontrado e 1 caso encontre o elemento pesquisado
    if(v[m] == num || v[m] == num+1) return 1;
  • seu algoritmo não faz uma pesquisa ternária, ele apenas pesquisa o primeiro terço do vetor em busca do elemento pesquisado e caso o elemento esteja nos outros dois terços do vetor entra em loop.

Como o Stack Overflow não é uma mídia presencial é mais fácil descartar e implementar um novo algoritmo do que corrigir.

Primeira coisa a se deixar claro é o conceito de pesquisa ternária.

Uma pesquisa ternária é um técnica de pesquisa que usa uma estratégia de divisão e conquista para determinar a posição de um valor específico em um vetor classificado, no caso em ordem crescente.
Enquanto que na busca binária o vetor é dividido em dois campos de pesquisa, na pesquisa ternária o vetor é dividido em três campos de pesquisa os terços direito, central e esquerdo, seguindo o sentido de leitura ocidental.
Seu algoritmo pode ser implementado de forma iterativa ou recursiva, no exemplo será implementado de forma iterativa.

Um algoritmo iterativo de pesquisa ternária recebe como entradas um vetor classificado em ordem crescente mais um valor a ser buscado o índice, e:

  • determina os índices do primeiro e do último elementos do vetor que será o campo de pesquisa.
  • enquanto o índice do primeiro elemento do escopo de pesquisa for menor ou igual ao o índice do último elemento do campo de pesquisa...
    • a partir do comprimento do campo de pesquisa determina os índices dos terços direito e esquerdo.
    • verifica, caso o elemento cujo índice é o terço direito seja igual ao valor buscado abandone a função retornado o índice terço direito.
    • verifica, caso o elemento cujo índice é o terço esquerdo seja igual ao valor buscado abandone a função retornado o índice terço esquerdo.
    • verifica, caso o valor do buscado seja menor ao elemento cujo índice é o terço direito:
      • determina que o índice do final campo de pesquisa será o índice do terço direito menos 1.
      • continua com a próxima iteração.
    • verifica, caso o valor do buscado seja maior ao elemento cujo índice é o terço esquerdo:
      • determina o índice do inicial do campo de pesquisa será o índice do terço esquerdo mais 1.
      • continua com a próxima iteração.
    • determina que o campo de pesquisa será o índice do terço central.
  • como o elemento não foi encontrado retorna -1.
#include <stdio.h>
#include <stdlib.h>

int buscaTernaria(int size, int *arr, int num);

int main(){
    int n = 10;                                     //Tamanho do vetor
    int v[] = {6,8,27,53,104,225,369,507,801,999};  //Vetor
    int num = 801;                                  //Numero a ser pesquisado

    int pos = buscaTernaria(n, v, num);
    if(pos != -1) printf("O número %d é elemento %d do vetor", num, pos);
    else printf("Número não encontrado como elemento do vetor");
}

int buscaTernaria(int size, int *arr, int num){
    int inicio = 0;
    int fim = size-1;

    while(inicio<=fim){
      int terco_direito = inicio + (fim - inicio )/3;
      int terco_esquerdo = fim - (fim - inicio )/3;
      if (num == arr[terco_direito]) return terco_direito;
      if (num == arr[terco_esquerdo]) return terco_esquerdo;
      if (num < arr[terco_direito]){
        fim = terco_direito - 1;
        continue;
      }
      if (num > arr[terco_esquerdo]){
        inicio = terco_esquerdo + 1;
        continue;
      }
      inicio = terco_direito + 1;
      fim = terco_esquerdo - 1;
    }
    return -1;
}
//O número 801 é elemento de índice 8 do vetor

Teste o exemplo no ideone.com

1
  • 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;
}
0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .