Procura binária no PHP

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:

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:

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