Inércia Sensorial

15 de May de 2007

Procura binária no PHP

Filed under: PHP — inerte @ 22:41

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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:

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

2 Comments »

  1. 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 🙂

    Comment by Vinicius — 22 de May de 2007 @ 19:31

  2. É, 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!

    Comment by inerte — 22 de May de 2007 @ 22:57

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress