Pesquisa Simples (Linear)

Para começar vamos entender antes o que é uma pesquisa simples. Vamos supor que temos o seguinte conjunto de números:

Nesse conjunto queremos buscar o número destacado para tal supondo que a lista está ordenada e não podemos buscar diretamente um elemento visualmente vamos para a pesquisa simples que consiste em passar por todos os números da lista até chegar no 7 para isso temos que seguir a seguinte etapa:

Logo teremos que percorrer 7 casas de 10 no array para conseguirmos o número que queremos mas isso é ruim pois leva-se muito tempo para chegar no resultado e tempo é dinheiro então para isso temos a pesquisa binária que tem um lema de dividir para conquistar

Pesquisa Binária

A pesquisa binária tem o propósito de dividir para conquistar tende a ser mais efetiva quanto maior a quantidade de número presentes começamos definindo qual é o número mais baixo, o número mais alto e o meio que é dado por (Baixo + Alto)/2.

Nesse ponto o Baixo e o Alto são auto-explicativos mas o meio pode parecer um pouco confuso levando em conta que para definirmos o meio seria (Baixo + Alto)/2 que resultaria 5.5 mas sempre arredondaremos esse número para baixo.

Voltando nossa premissa do dividir para conquistar vamos chuta que nosso número escolhido esteja no meio, obviamente está errado mas ai que vamos diminuir as nossas tentativas pela metade descobrindo se esse chute é maior ou menor que nosso número.

• Caso seja maior => descartamos todos os número que vem antes do chute/meio e ele mesmo
• Caso seja menor => descartamos todos os número que vem depois do chute/meio e ele mesmo

Nesse caso é maior logo nossas possibilidades foram reduzidas para:

E agora se você analisar um pouco é somente questão de repetição logo nossas próximas possibilidades são:

Mais uma vez nosso chute(meio) está incorreto mas como somente temos duas alternativas chegamos a uma conclusão:

Ou seja levamos 4 tentativas de 10 comparado com a outra que foi 7/10 foi um grande progresso. Entretanto você pode se questionar que se nosso número fosse 1 invés de 7 o linear era bem mais efetivo que nossa pesquisa binária e de fato está correto mas do mesmo jeito se o array tivesse 100 números o nosso número fosse 50 o linear levaria 50 tentativas a binária levaria no máximo 7 e considerando que 50 é meio acertaria em 1 tentativa.

Logo considerando cada tipo de lista e seu tamanho você pode optar por um ou por outro, o linear é mais fácil de fazer e para números pequenos pode ser perfeito, mas para números grandes apesar de complexo o linear é a solução que pode ser mais efetiva.

Bônus - Exemplo em java

public static Integer binarySearch(List<Integer> array, Integer num) {

    int baixo = 0;  
    int alto = array.size() - 1;

    array.sort(Comparator.naturalOrder());

    while (baixo <= alto) {
        int meio = (baixo + alto) / 2;
        int chute = array.get(meio);

        if (chute == num) {
            return meio;
        } else if (chute > num) {
            alto = meio - 1;
        } else {
            baixo = meio + 1;
        }
    }
    return null;
}


public static Integer linearSearch(List<Integer> array, Integer num) {
    array.sort(Comparator.naturalOrder());
    for (int i = 0; i < array.size(); i++) {
        if(array.get(i) == num) return i;
    }
    return null;
}

Big O Notation - Qual a performance do seu algoritmo?

Já se pergunto se seu algoritmo é mais rápido do que o de pessoa X mas nunca conseguiu entender como medir o desempenho/eficiência agora vamos descobrir analisando os dois algoritmos de busca acima:

Pesquisa Simples

No big O temos algumas representações de performance e uma de delas é O(n) basicamente a performance desse algoritmo no pior dos casos vai ser percorrer todos os items do array n logo a performance da pesquisa simples em um array que tem 100 items será de O(100) ou seja no pior dos casos teremos que fazer 100 interações

Pesquisa Binária

Já em contraste com nossa pesquisa simples que leva O(n) nosso algoritmo de pesquisa binária usa O(Log2 n) ou seja a performance do nosso algoritmo é dado por logaritmo com base 2 do número de items dentro do array, logo na pior das hipóteses considerando um array de 100 nosso algorítimo iria levar O(Log2 100) de tentativas ou seja aproximadamente 7 tentativas para achar o número escolhido no pior dos casos

Considerações finais

Toda informação neste artigo foi baseado no capítulo 1 do livro Entendendo Algoritmos de Aditya Y. Bhargava, no livro o conteúdo é bem mais completo e com mais detalhes o artigo é mais um mini resumo do capítulo com o intuito de lembrar dos conceitos bases e com meu ponto de vista sobre o assunto.