image

Acesse bootcamps ilimitados e +650 cursos pra sempre

60
%OFF
Weslley Ferraz
Weslley Ferraz15/01/2024 06:55
Compartilhe

Ánalize de Algoritimos: Tipos de Busca - Busca Ordenada

    Na análise de algoritmos e estruturas de dados, a eficiência das buscas pode ser aprimorada de diversas maneiras quando a lista está ordenada, seja de modo crescente ou decrescente. Em situações em que a lista não está ordenada, são necessárias "n" comparações para encontrar o valor desejado. No entanto, quando lidamos com listas ordenadas, o número de comparações necessárias é reduzido pela metade, totalizando apenas "n/2" comparações.

    Esse ganho de eficiência em listas ordenadas é crucial para otimizar o desempenho de algoritmos de busca. Ao aproveitar a ordenação prévia, é possível implementar técnicas específicas que diminuem a complexidade temporal das operações de busca. Dentre essas técnicas, destacam-se algoritmos como a busca binária, que efetua sucessivas comparações descartando metade da lista em cada passo.

    Vamos ilustrar isso com um exemplo prático em linguagem C, utilizando a busca binária para encontrar um elemento em uma lista ordenada:

    #include <stdio.h>
    #include <locale.h>
    
    
    // Função de busca binária em uma lista ordenada
    int busca_binaria(int lista[], int tamanho, int elemento) {
      int inicio = 0;
      int fim = tamanho - 1;
      int meio;
    
      // Laço de busca continua enquanto a sublista não estiver vazia
      while (inicio <= fim) {
          // Calcula o ponto médio da sublista
          meio = (inicio + fim) / 2;
    
          // Verifica se o elemento está no meio da sublista
          if (lista[meio] == elemento) {
              return meio; // Elemento encontrado, retorna a posição
          } else if (lista[meio] < elemento) {
              inicio = meio + 1; // Descarta a metade inferior da sublista
          } else {
              fim = meio - 1; // Descarta a metade superior da sublista
          }
      }
    
      return -1; // Elemento não encontrado na lista
    }
    
    
    int main() {
      setlocale(LC_ALL, "Portuguese");
    
      // Lista de exemplo (deve estar ordenada para a busca binária)
      int lista[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
      int tamanho = sizeof(lista) / sizeof(lista[0]); // Calcula o tamanho da lista
      int elementoProcurado = 8;
    
      // Chama a função de busca binária
      int resultado = busca_binaria(lista, tamanho, elementoProcurado);
    
    
      // Verifica se o elemento foi encontrado e exibe a mensagem apropriada
      if (resultado != -1) {
          printf("Elemento encontrado na posição %d.\n", resultado);
      } else {
          printf("Elemento não encontrado na lista.\n");
      }
    
      return 0;
    }
    

    Neste exemplo, a função busca binária utiliza a busca binária para encontrar um elemento em uma lista ordenada, minimizando o número de comparações necessárias. Essa é apenas uma das muitas técnicas que podem ser aplicadas para otimizar algoritmos de busca em estruturas de dados ordenadas.

    Compartilhe
    Comentários (0)