ALGORITHMS - BUSCA BINÁRIA

Algoritmos são sequências de instruções para se resolver um determinado problema, contudo eles podem variar em efiência e perfomance para resolução do mesmo. Dito isto, seu estudo é importante para qualquer programador, pois muitas vezes ja pegamos "coisas prontas" e usamos indiscriminadamente sem entender os trade-offs das mesmas. Isso limita o programador e sua visão criativa/resolutiva, ou seja, ele é dominado pelas ferramentas que usa.

Conceitos Básicos

O algoritmo que iremos ver é o de busca binária (binary search), sendo o nome bem sugestivo podemos ter uma ideia do problema que ele resolve.

Imaginemos que você tenha que achar a pagina 567, porque por algum motivo você perdeu o marcador de novo, em um livro de 1000 paginas. Como você faria essa busca ? O mais comum a se fazer seria começar a busca pelo meio, certo ? Pois, a pagina 567 fica mais próxima do meio do livro. Com certeza, essa uma maneira bem mais rápida de buscar, do que olhar pagina por pagina.

O conceito de busca binária não é muito diferente do exemplo do livro, mas irei ilustrar com um exemplo um pouco melhor, menos livroso. Você está tentando adivinhar número de meias listradas (que é 57) que uma pessoa tem, ela irá te dizer se você disse um número muito acima ou baixo da atual quantidade, entre 1 a 100.

Há duas maneiras de resolver este problema:

Busca simples

Podemos começar pelo número 1, 2, 3, 4, 5... e assim por diante, estando essas tentativas muito abaixo do número atual de meias listradas e continuaremos a verificar item por item até o número desejado.

Busca binária

Outra opção seria começar pelo meio, no caso, o número 50 que ainda está abaixo da quantidade atual. Sabendo disso podemos eliminar a metade (1 a 50, nos restando de 51 a 100) e tentar novamente, por exemplo 58, mas ainda é um valor acima do número que procuramos, mais uma vez eliminamos a metade (de 58 a 100, nos restando de 52 a 57) e tentamos novamente. Podemos tentar agora 57 e acertamos a quantidade das benditas meias listradas. Veja o exemplo escrito em C logo abaixo:

// Bem, aqui estamos passando uma lista de inteiros e o seu tamanho (uma cortesia do C)
int binary_search(int itens[], int length)
{
    int abaixo = 0;
    int acima = length - 1;

    // O nosso intuito é iniciar nossa busca pelo meio da lista
    int meio = length - 1 / 2;

    // Item que desejamos achar
    int item_desejado = 5;

    while (abaixo <= acima)
    {
        // Atualizando o nosso "novo meio"
        meio = abaixo + acima;

        // Nosso palpite sempre será o meio da nossa lista
        int palpite = itens[meio];

        // Se nosso palpite estiver certo, retornamos o lugar onde o item está
        if (palpite == item_desejado)
            return meio;

        // Caso esteja errado, iremos verificar se o palpite está muito acima ou abaixo do esperado
        if (palpite > item_desejado)
        {
            // Estando acima do esperado, cortamos metade das possibilidades acima
            acima = meio - 1;
        }
        else
        {
            // Estando abaixo do esperado, cortamos metade das possibilidades abaixo
            abaixo = meio + 1;
        }
    }


}

Contudo o algoritmo irá funcionar apenas com lista de dados ordenados, como [1,2,3] ou ["Ana", "Bob", "Carla"].

Mas você já deve estar conseguindo sentir o cheirinho das aplicações desse algoritmo no mundo real, como consultas em banco de dados ou pesquisa de uma música na sua playlist (se ordenada).