Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
Como usar a busca binária em C - Pesquisa binária na linguagem CQuantidade de visualizações: 586 vezes |
A busca binária, ou pesquisa binária, é um algoritmo eficiente para encontrar um item em uma lista (vetor ou array) ordenada. Sim, os itens devem, obrigatoriamente, estar ordenados. O processo é bem simples. A busca binária começa a partir do meio da lista e compara o item nesta posição com o valor sendo pesquisado. Se o valor não for encontrado e for menor que o item no meio da lista, o algoritmo passa para a porção à esquerda da lista, eliminando, assim, metade dos elementos do vetor ou array (a porção maior que o valor pesquisado). Se o valor não for encontrado e for maior que o item no meio da lista, então a busca reinicia a partir da metade da sub-lista à direita (os itens maiores que o valor pesquisado). Essa divisão continua até que o valor seja encontrado ou não seja mais possível dividir a lista pela metade. Se um array ou vetor possuir 100 elementos e usarmos a busca binária nele, precisaremos efetuar no máximo 7 tentativas para encontrar o valor desejado. Se a lista possuir 4 bilhões de itens nós teremos que fazer no máximo 32 tentativas. Isso acontece porque a pesquisa binária é executada em tempo logarítmico, ou seja, log2 n, onde n é a quantidade de itens no vetor. Dessa forma, se tivemos 1.000 itens em um array, log2 1000 = 10 tentativas. Lembre-se de que, na programação log e log2 retornam resultados diferentes: log(10) = 2.302585092994046 enquanto log2(10) = 3.321928094887362. Na análise da busca binária nós usamos sempre log2. Vamos agora ver como podemos codificar a busca binária em C. Veja o código a seguir: #include <stdio.h> #include <stdlib.h> #include <locale.h> #define TAM_ARRAY 10 // função principal do programa int main(int argc, char *argv[]){ setlocale(LC_ALL,""); // para acentos do português // variáveis para ajudar na resolução do problema int i, numero, esquerda, direita, meio, encontrado; // vamos criar uma um vetor ordenado de inteiros int valores[] = {3, 5, 7, 8, 9, 12, 43, 50, 52, 60}; // vamos mostrar os elementos do vetor printf("Os valores do array são: "); for(i = 0; i < TAM_ARRAY; i++){ printf("%d, ", valores[i]); } // vamos pedir o item a ser pesquisado printf("\n\nInforme o número a ser pesquisado: "); scanf("%d", &numero); // agora vamos pesquisar o número no array usando a pesquisa // binária // a variável esquerda aponta para o primeiro elemento do vetor esquerda = 0; // a variável direita aponta para o último elemento do vetor direita = TAM_ARRAY - 1; // para indicar se o valor foi encontrado encontrado = 0; // enquanto houver mais de um elemento a ser comparado Ao executar este código C nós teremos o seguinte resultado: Os valores da lista são: [3, 5, 7, 8, 9, 12, 43, 50, 52, 60] Informe o número a ser pesquisado: 9 O número foi encontrado no índice 4 |
![]() |
Desafios, Exercícios e Algoritmos Resolvidos de C |
Veja mais Dicas e truques de C |
Dicas e truques de outras linguagens |
Delphi - Como converter strings em valores TDateTime usando as funções StrToDate() e StrToDateDef() do Delphi |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
1º lugar: Java |