A pesquisa binaria é um algoritmo muito eficiente para busca de um item em uma lista ordenada de itens. Ela funciona dividindo a lista no meio e analisando se o item a ser encontrado é maior menor ou até mesmo igual ao item central da lista, como no exemplo abaixo:
E aqui o código em linguagem C utilizado para a pesquisa binaria:
No algoritmo de Busca Binaria temos sempre um caso onde ele se sai melhor se comparado a busca sequencial por exemplo, porém na maioria dos casos a busca se torna bem eficiente.
O melhor caso para esse algoritmo é quando o item a ser buscado está exatamente no meio da lista tornando assim a complexidade de tempo de O(1), ou seja, o algoritmo precisou realizar apenas uma iteração/comparação. O pior caso é quando o valor a ser buscado não se encontra na lista.