Á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.