Pesquisa binária – Wikipédia, a enciclopédia livre
Pesquisa binária | |
---|---|
classe | Algoritmo de busca |
estrutura de dados | Array |
complexidade caso médio | |
complexidade melhor caso | |
complexidade de espaços pior caso | |
otimo | Sim |
espaço | |
Algoritmos | |
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
Análise de Complexidade
[editar | editar código-fonte]A complexidade desse algoritmo é da ordem de [1], em que é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é [2].
Procedimento
[editar | editar código-fonte]Dado uma lista de elementos com os valores , , , , ordenada de tal modo que , e um valor para pesquisa , a seguinte rotina usa pesquisa binária para achar o índice de em .
- Defina para 0 e para
- Se a pesquisa termina sem sucesso
- Defina (o índice do meio da lista) para arredondado
- Se , defina para e volte ao segundo passo
- Se , defina para e volte ao segundo passo.
- Se , a pesquisa está feita, o índice de é
Implementações
[editar | editar código-fonte]Pseudo-Código
[editar | editar código-fonte]Um pseudo-código recursivo para esse algoritmo, dados V
o vetor com elementos comparáveis e e
o elemento que se deseja encontrar:
BUSCA-BINÁRIA(V[], início, fim, e) i recebe o índice do meio entre início e fim se (v[i] = e) entao devolva o índice i # elemento e encontrado fimse se (inicio = fim) entao não encontrou o elemento procurado senão se (V[i] vem antes de e) então faça a BUSCA-BINÁRIA(V, i+1, fim, e) senão faça a BUSCA-BINÁRIA(V, inicio, i-1, e) fimse fimse
Código em C
[editar | editar código-fonte]//Implementação Iterativa: int PesquisaBinaria (int vet[], int chave, int Tam) { int inf = 0; // limite inferior (o primeiro índice de vetor em C é zero ) int sup = Tam-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números) int meio; while (inf <= sup) { meio = (inf + sup)/2; if (chave == vet[meio]) return meio; if (chave < vet[meio]) sup = meio-1; else inf = meio+1; } return -1; // não encontrado } //Implementação Recursiva: // x => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita) int PesquisaBinaria (int x, int v[], int e, int d) { int meio = (e + d)/2; if (v[meio] == x) return meio; if (e >= d) return -1; // não encontrado else if (v[meio] < x) return PesquisaBinaria(x, v, meio+1, d); else return PesquisaBinaria(x, v, e, meio-1); }
Obs: A linguagem C fornece a função bsearch
[3] na sua biblioteca padrão.
Ver também
[editar | editar código-fonte]Referências
- ↑ Felipe, Henrique (6 de setembro de 2017). «A Busca Binária». Blog Cyberini. Consultado em 8 de julho de 2018
- ↑ Felipe, Henrique (14 de setembro de 2017). «Busca Linear». Blog Cyberini. Consultado em 8 de julho de 2018
- ↑ «bsearch(3): binary search of sorted array - Linux man page». linux.die.net (em inglês). Consultado em 8 de julho de 2018
Ligações externas
[editar | editar código-fonte]- Projeto de Algoritmos - Paulo Feofiloff -IME-USP
- NIST Dicionário de Algoritmos e Estrutura de Dados :binary search
- Tim Bray. On the Goodness of Binary Search. Pequeno ensaio das vantagens da busca binária e exemplo de código em Java.
- Google Research: Nearly All Binary Searches and Mergesorts are Broken
- Busca binária em Java e em C