b) Pesquisa Binária

A pesquisa binária é uma forma mais eficiente de efetuarmos a pesquisa, entretanto tem como pré-requisito a necessidade de a lista estar ordenada.

O conceito da pesquisa binária é simples. Vamos usar a lista de valores do exemplo anterior ordenada e buscaremos o valor 6:

Tomando por base a lista ordenada, o primeiro passo da busca binária será comparar o valor procurado com aquele da posição central da lista ordenada. Como o valor procurado 7 é maior que 5, então sabemos que o valor procurado está necessariamente à direita do valor central:

Iremos novamente buscar o elemento central. Como temos um número par de elementos, então iremos comparar o valor procurado com o valor central à esquerda que é 7. Como 7 é maior que o valor procurado, então sabemos agora que o valor procurado está à esquerda do elemento central:

Novamente temos um número par de células, e o elemento que iremos comparar com o valor procurado será o elemento central da esquerda, ou seja, o valor 6. Como o valor é igual então poderemos terminar nossa busca por aqui. Se o valor não fosse igual, poderíamos concluir que o valor não existe na lista.