O algoritmo de Procura Binária é, de um modo geral, o mais eficiente (demora menos tempo a encontrar o valor), mas requere que a lista em que a procura vai ser efectuada esteja ordenada (vamos supor que a ordenação é por ordem crescente).
O algoritmo selecciona um valor no meio da lista e compara-o com o valor que está a procurar.
Se o valor a procurar for maior que o valor seleccionado, repete o processo para a metade da lista posterior ao valor seleccionado
.
Se o valor a procurar for menor que o valor seleccionado, repete o processo para a metade da lista anterior ao valor seleccionado.
O processo é repetido até um valor ser encontrado, ou até a metade em que a procura deverá ser feita ser vazia (neste caso o valor não está na lista).
O algoritmo para procurar na lista de Reais é apresentado no algoritmo 4.6. O processo de adaptação do algoritmo é idêntico ao mostrado nas duas secções anteriores. A partir de aqui, fica como exercício fazer a adaptação dos algoritmos a outras estruturas de dados.
