Pesquisa Binária ou Logarítmica

A pesquisa binária é muito utilizada quando se quer ganhar tempo na pesquisa. Geralmente a pesquisa binária é utilizada quando temos muitos elementos.

Se fôssemos aplicar a pesquisa binária no exemplo do baralho, deveríamos reparti-lo ao meio e verificar se a carta que apareceu está antes ou depois daquela que estamos procurando. Caso estejamos longe da carta procurada, devemos descartar a metade mais distante e repartir novamente o bolo do baralho. E assim seguimos até encontrar a carta desejada. Veja que, para isso funcionar, o baralho deve estar na ordem, ou gastaremos muito tempo na procura.

A pesquisa binária ou logarítmica é uma otimização do algoritmo simples, no entanto, neste caso, é necessário que a lista esteja ordenada. A busca consiste em pegar o elemento central da lista e comparar com o valor a ser buscado, caso o elemento esteja na parte superior da lista, a parte inferior é descartada e o processo se repete.

A figura abaixo representa um elemento em uma lista a ser encontrado.