Pesquisa binária

Há uns meses atrás eu comprei um livro sobre algoritmos na Amazon e o li até um pouco mais que a metade. Entretanto a minha ideia era de ir escrevendo os algoritmos numa linguagem que estou acostumado para praticar o que foi aprendido. Mas infelizmente eu só passei pelos capítulos na leitura e não cheguei a produzir nenhum código efetivo.

Porém nestes últimos dias eu voltei a ler este livro do início e desta vez eu pretendo sempre escrever em javascript o código prático referente ao algoritmo explicado no capitulo.

Sobre o livro

O livro em questão se trata deste aqui:

Pelo que eu li, eu poderia dizer que o autor se esforçou para produzir uma obra bem didática. Suas explicações são muito boas e ele usa bastante de figuras para embasar seus exemplos. Neste livro ele não aborda todos os algoritmos, mas mesmo assim apresenta os principais como meio de te introduzir neste conhecimento.

Se você já mexe com programação a algum tempo, se já chegou a desenvolver vários scripts, sistemas pequenos ou similares. Eu lhe aconselharia a compra desta obra caso você se interesse por isso. E caso você realmente deseja comprar eu deixarei abaixo o meu link de afiado da amazon para a compra deste livro logo abaixo.

Agora vamos ao que interessa!

Sobre a pesquisa binária

Se você já programa a algum tempo, é muito provável que você já tenha feito a seguinte instrução genérica em alguma linha de código. Segue um exemplo abaixo.

let numeric_list = [1,2,3,4,5,6,7,8,9,10];
let find_number = 9;
numeric_list.forEach((number_value, number_index) {
    if(number_value == find_number ) {
        console.log('Número encontrado: ' + number_value);
    }
});

Ou seja, você possui uma coleção de dados ordenados armazenados num array. Porém em algum momento do código você vai precisar fazer uma pesquisa dentro deste array para recuperar um valor específico.

Infelizmente esta sua pesquisa vai precisar percorrer por cada um dos elementos do array até que se encontre o valor desejado. No exemplo acima, a lista numérica é tão pequena que a duração do processamento deste script é totalmente desprezível. Porém, vamos imaginar que temos uma lista ordenada contendo milhões e milhões de informações. Você acha válido o loop rodar por milhares de vezes até que se encontre a informação desejada?

Vamos supor que a lista numérica acima possui uma listagem de tamanho 1.000.000. E agora imagina que o número que você precisa encontrar seja 999.999. Nestas condições o loop vai precisar rodar quase um milhão de vezes apenas para encontrar o número desejado.

E se eu te contar que existe um algoritmo capaz de reduzir esta quantidade excessiva de loops para um número muito menor, você acreditaria? São nestas horas que algoritmos como busca binária nos poupam de loops desnecessários.

A busca binária

A ideia deste algoritmo é bem simples. Imagine que você queira consultar por algum nome no dicionário. Você nunca vai começar a busca igual a um loop for, passando de página em página, palavra por palavra até encontrar a palavra desejada. Na verdade, se a palavra desejada for por exemplo o meu nome “MAICKON”. Uma pessoa normal, iria abrir o dicionário numa página onde fossem listados os nomes que começam com a letra M.

E é mais ou menos desta forma que o algoritmo funciona. Você simplesmente acesso o meio da lista e faz uma pergunta.

“O número desejado está a frente do meio da lista ou está atrás do meio da lista?”

Respondendo a esta pergunta, você vai sempre eliminando metade da lista a cada pergunta. Desta forma, se formos seguindo o exemplo do script acima, o fluxo seria mais ou menos assim.

Minha lista tem números de 1…10. Eu preciso encontrar o número 9. Eu simplesmente acesso o meio da lista que seria o valor 5. Então eu pergunto. O número desejado que é 9 é maior do que 5 ou menor do que 5? Se o número for maior do 5 eu simplesmente ignoro os números de 1 a 4 e passo a tomar como referência os número de 5 a 10 e refaço a minha pergunta. Após cortar novamente pela metade este intervalo de 5 a 10. Nesta parte você pode arredondar tanto para cima como para baixo, pois para facilitar o nosso processo, deixamos sempre o número comparativo como um inteiro. Então, seguindo o fluxo, vamos definir como metade o número 8. Daí eu faço novamente a pergunta. O número desejado é maior ou menor que 8? Como 9 é maior do que 8, refazermos a mesma pergunta para 9 e 10 até chegarmos no nosso número procurado.

A grande vantagem deste método é que nós fomos capazes de encontrar o resultado 9 com apenas algumas etapas de verificação. No modelo anterior nós precisamos passar por 9 verificações até que fosse encontrado o número desejado. Mas usando a pesquisa binária, foi possível descobrir o número desejado com bem menas etapas.

E o código? Como seria a implementação disso

O código a seguir vai exemplificar a execução de duas funções em javascript. A primeira vai executar a busca por um número numa lista ordenada de mil elementos.

No script você vai perceber que o loop percorre a lista até que encontre o valor desejado.

//declaração de um array vazio 
let list = [];
//um loop até 1000 para preencher de forma ordenada o array list 
for(let i=0; i<=1000; i++) {
    list.push(i);
}

//Esta função percorre o array list em busca de encontrar o valor passado por 
//parâmetro em item.
function simpleSearch(list, item) {
    //Pesquisa simples
    let simple_operatios = 0;
    list.forEach((v,i) => {
    if(v == item) {
        console.log('[Simples] Operacoes: '+simple_operatios);
        return 0;
    }
    simple_operatios++;
    });
}

//Esta função faz uso do algoritmo de pesquisa binária para encontrar o número 
//desejado no menor número de operações possível.
function binarySearch(list, item) {
    //definimos o índice do menor valor do array 
    let min = 0;
    //definimos o índice do maior valor do array
    let max = list.length-1;
    //definimos um contador parado número de operações 
    let simple_operations = 0;

    //Enquanto o índice mínimo for menor ou igual ao índice máximo. O loop deve rodar 
    while (min <= max) {
        //aqui definimos o índice que representa o valor que se encontra no meios do array
        //Observe que como se trata de um índice de array, o seu valor precisa ser um inteiro. Por isso o uso da função parseInt
        let half = parseInt((min+max)/2);
        //uma vez que temos o índice do valor central no array. 
        //Acessamos este array pelo seu índice central. Isso vai nos retornar o valor 
        //que está no meio do array 
        let sugestion = list[half];
        //Incrementa o contador de operações feitas
        simple_operations++;

        //verifica se o valor armazenado em sugestion é igual ao valor passado no 
        //parâmetro item. Caso seja, nós encontramos o nosso número desejado
        if(sugestion == item) {
            //exibe uma mensagem mostrando o número de operações realizada até 
            //chegar no resultado 
            console.log('[Binaria] Operacoes: '+simple_operations);
            //retornamos o valor encontrado 
            return list[half];
        }
        //Se o valor sugerido for maior que o valor desejado na procura
        //Nós atualizamos o valor do índice máximo para um índice que representa 
        //a metade da lista -1
        //O índice que representa a metade da lista está armazenado na variável half 
        if(sugestion > item) {
            max = half - 1;
        } else {
            //Caso contrário nós acrescentamos +1 no índice que representa a metade da lista 
            min = half +1;
        }
    }

    return null;
}

//Quando as duas funções são executadas nós vamos reparar que a função que 
//faz uso da pesquisa binária possui um número inferior de operações com relação 
//a pesquisa feita de forma linear onde a cada loop, haverá uma verificação 
simpleSearch(list, 77);
binarySearch(list, 77);

Bem pessoal, eu espero que este artigos lhe sirva como um agregador de conhecimento.

Agora você sabe que quando precisar percorrer por uma longa lista ordenada, você poderá usar um algoritmo que chegará a um resultado de forma muito mais rápida que dá maneira convencional.