Pesquisa binária
A pesquisa ou busca binária é 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.
A complexidade desse algoritmo é da ordem de Θ ( log 2 n ) {\displaystyle \Theta (\log _{2}n)} , em que n {\displaystyle n} é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O ( n ) {\displaystyle O(n)} .
Dado uma lista A {\displaystyle A} de n {\displaystyle n} elementos com os valores A 0 {\displaystyle A_{0}} , A 1 {\displaystyle A_{1}} , A 2 {\displaystyle A_{2}} , . . . {\displaystyle ...} , A n − 1 {\displaystyle A_{n-1}} ordenada de tal modo que A 0 ≤ A 1 ≤ A 2 ≤ . . . ≤ A n − 1 {\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq ...\leq A_{n-1}} , e um valor para pesquisa T {\displaystyle T} , a seguinte rotina usa pesquisa binária para achar o índice de T {\displaystyle T} em A {\displaystyle A} .
Pseudo-Código
Um pseudo-código recursivo para esse algoritmo, dados V o vetor com elementos comparáveis e e o elemento que se deseja encontrar:
Código em C
Obs: A linguagem C fornece a função bsearch na sua biblioteca padrão.
