Algoritmos de Busca

Uma das coisas mais comuns em desenvolvimento de software é a necessidade de se buscar algo, seja em uma lista ou em uma tabela, array, ou qualquer outra estrutura que armazene um número n de dados. ¯\_(ツ)_/¯

Um algotitmo de busca é aquele que aceita um argumento 'a' e tenta encontrar o registro cuja chave seja 'a'.

Sendo assim, dado um conjunto de elementos, onde cada um é identificado por uma chave, o objetivo da busca é encontrar o elemento que corresponde a uma determinada chave.

Enfim... Segue alguns algoritmos.

OPA! E, por favor, lembre que isso aqui é feito por um estudante! Se encontrar um erro, ou conhecer um formato melhor, cria uma issue com o seu conteúdo! :D

Busca Sequencial

Essa é a forma mais simples de busca. Basicamente, percorre-se elemento por elemento em busca do correspondente à chave.

A Busca Sequencial, no pior caso, é O(n).

        int search(int key, int v[]) {
        ..int i;
        .
        ..for (i = 0; i < n; i++) {
        ....if (v[i] == key) return i; //Encontrou a chave na posição i.
        ..}
        ..return -1; Não encontrou a chave.
        }
      

Busca Binária

Nesse tipo de busca, é necessário que os elementos estejam ordenados. Assim, a Busca Binária vai comparar o elemento buscado com o elemento do meio do vetor.

Se igual, encontrou.
Se menor, busca-se apenas na metade da esquerda.
Se maior, busca-se apenas na metade da direita.

A complexidade é O(log n), porque cada comparação reduz o range de busca por um fator de 2.

        int bb(int key, int n, int v[]) {
        ..int l, m, r;
        ..r = n - 1;
        ..l = 0;
        ..while (l < r) {
        ....m = (l + r) / 2;
        ....if (v[m] < key) l = m + 1;
        ....else r = m;
        ..}
        ..return (v[l] == key)? l: -1;
        }
      