Pesquisa binária: dividir a pesquisa ao meio — Informática, 7–10
Quando uma lista já está ordenada, não precisas de verificar cada item um a um. A pesquisa binária começa pelo meio, decide em que metade pode estar a resposta e repete o processo até encontrar o item ou concluir que não existe.
Cortar sempre as possibilidades ao meio
Imagina que um número secreto está escondido numa fila ordenada. Em vez de começares pelo primeiro número, pergunta pelo que está no meio. Se o alvo for maior, ignora a metade de baixo; se for menor, ignora a metade de cima. Cada resposta elimina cerca de metade das escolhas, por isso a pesquisa fica rapidamente pequena.
Porque não verificar todos os itens?
Começar pelo princípio funciona numa lista curta, mas fica lento quando há milhares ou milhões de itens ordenados. A pesquisa binária usa a ordem como pista, em vez de desperdiçar essa pista. Nasceu de uma pergunta sensata: como podemos eliminar o maior número possível de lugares errados com uma só verificação?
Encontrar 73 numa lista
A lista ordenada é 12, 25, 31, 44, 58, 73, 81, 90. Primeiro, verifica o meio: 44. Como 73 é maior, mantém 58, 73, 81, 90. Verifica o meio destes números: 73. O alvo é encontrado após duas verificações, em vez de serem verificados os oito números desde o início.
A ordem é essencial
É razoável usar o meio de qualquer lista, porque o meio parece um atalho útil. Mas, se a lista for 12, 90, 25, 73, 44, 81, 31, 58, ver 44 não te diz em que metade está 73. A pesquisa binária só funciona quando a lista está ordenada pela mesma coisa que estás a comparar.
Encontrar coisas rapidamente
Um dicionário usa a ordem alfabética, por isso podes abri-lo perto do meio e reduzir a pesquisa de uma palavra. Os programas usam a mesma estratégia com nomes, números e registos ordenados. É útil quando a lista é grande e já está ordenada; ordená-la primeiro pode dar trabalho extra, por isso o atalho nem sempre é a melhor escolha.
Continua a explorar
Outras línguas
A carregar o MyLeoNes™…