Inércia Sensorial

Procura binária no PHP

Comments 15 dAmerica/Los_Angeles May, 2007 sob PHP.
Tags:

Uma coisa é certa, a função in_array do PHP é devagar, lerda demais.

Existe uma alternativa para pesquisar se o elemento está na matriz chamada "procura binária", que aliás, tanto faz a linguagem que você usa, as idéias são as mesmas. O conceito é simples, ver se o item está no meio da matriz, se não estiver, cortar ela no meio, ver se está na metade, se não estiver, cortar a metade ao meio, ad infinitum, ou até que dure.

Imagine que você tenha de procurar o nome "Julio Nobrega" na lista telefônica. Ir de item em item e ver se cada um equivale ao termo é loucura. Oras, abra a lista bem no meio e veja o nome, se ele for Julio Nobrega, pronto. Se não for, o nome que está no meio, é maior ou menor que o nosso termo? Se for maior, parta na metade a lista e procure na primeira parte. Eliminamos 50% de onde vamos procurar num piscar de olhos. Repita isso, e o espaço de procura vai diminuindo até só sobrar o termo pesquisado. Muito melhor que um por um.

Lá vai a função:

PLAIN TEXT

PHP:

function procura_binaria($elemento, $matriz)
{
$baixo = 0;
$alto = sizeof($matriz) - 1;
while ($baixo <= $alto) {
$meio = floor(($baixo + $alto) / 2);
if ($elemento == $matriz[$meio]) {
return $matriz[$meio];
} else {
if ($elemento <$matriz[$meio]) {
$alto = $meio - 1;
} else {
$baixo = $meio + 1;
}
}
}
return false; // Não achou!
}

Usar é moleza:

PLAIN TEXT

PHP:

if (!pesquisa_binaria($termo, $matriz)) {
echo 'Não achou!';
}

inerte

É, heh :) Esqueci de mencionar a ordenação.

Quanto à matriz, array, vetor, lista, dicionário, tabela, às vezes eu me confundo todo :p você está corretíssimo.

Em retrospecto, minha escrita pecou nesses erros.. obrigado pelos avisos!

Vinicius

a in_array encontra o elemento mesmo se o array não estiver ordenado... se vc precisar ordenar o array antes, não compensa usar a pesquisa binária...

ah, e sendo chato: o correto é array ou vetor... matriz tem duas dimensões :)