- Valor procurado
- Ainda possíveis
- Comparados
- Excluídos
- Encontrados
Pesquisa binária
A pesquisa binária encontra um valor numa lista ordenada olhando sempre para o meio. Se o valor do meio for demasiado pequeno, o alvo só pode estar depois dele; se for demasiado grande, só antes. Em qualquer caso, metade do que resta fica excluída. Escolha o valor a procurar, avance pela pesquisa passo a passo e veja a parte sombreada encolher até o alvo ser encontrado ou não restar nada. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A linha tracejada marca o valor que procura, e a parte sombreada mostra onde ainda pode estar. A pesquisa binária precisa de uma lista ordenada, por isso uma lista desordenada é ordenada primeiro. Escolha o valor, quantas barras, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escolha o valor a procurar e quantas barras. Ou escreva os seus próprios números: a pesquisa binária ordena-os primeiro.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
- Compare o contador Comparações com «A pesquisa linear precisaria de», para um valor perto do fim ou um que não exista.
Como funciona a pesquisa binária
Acompanhe a parte da lista ordenada que ainda pode conter o alvo; no início, é a lista inteira. Olhe para o valor no meio dela. Se for igual ao alvo, terminou. Se for menor, o alvo só pode estar depois dele, por isso continue com a parte a seguir ao meio. Se for maior, continue com a parte anterior. Quando não restar nada, o alvo não está na lista.
Porque é tão rápida
Cada comparação reduz para metade a parte que resta. Partindo de n valores, após k comparações restam no máximo cerca de n/2ᵏ, por isso a pesquisa termina após, no máximo, ⌊log₂ n⌋ + 1 comparações: 6 para 40 valores, 10 para 1000, 20 para um milhão. A pesquisa linear pode ter de ver todos os valores. O senão é que a lista tem de estar ordenada, e mantê-la ordenada, ou ordená-la primeiro, tem o seu próprio custo.
Perguntas frequentes
Como funciona a pesquisa binária?
Compara o alvo com o valor do meio da parte de uma lista ordenada que ainda o pode conter. Se forem iguais, encontrou-o; caso contrário, descarta a metade que não pode conter o alvo e continua na outra metade até encontrar o alvo ou não restar nada.
De quantas comparações precisa a pesquisa binária?
No máximo ⌊log₂ n⌋ + 1 para uma lista de n valores: 6 para 40, 10 para 1000, 20 para um milhão. Cada comparação reduz para metade o que resta.
Porque precisa a pesquisa binária de uma lista ordenada?
Porque só numa lista ordenada uma comparação lhe diz de que lado está o alvo. Numa lista desordenada, um valor menor no meio não diz nada sobre onde está o alvo, por isso não se pode excluir nada.
Que valor encontra quando há duplicados?
Qualquer um deles, consoante onde caem os meios. As variantes que continuam a procurar à esquerda ou à direita depois de uma correspondência encontram a primeira ou a última ocorrência.
Os meus números são enviados para algum lado?
Não. A pesquisa corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor