Busca binária

Anteriormente, utilizamos um algoritmo de busca chamado busca sequencial. Ele percorre o vetor até encontrar o valor desejado. No pior caso, quando o elemento não existe no vetor, todo o conjunto é percorrido até se perceber que o valor não existe naquela região de memória.

A busca binária é um algoritmo de busca eficiente usado para encontrar um determinado elemento em uma lista ordenada. Atenção: a busca binária assume que o vetor está ordenado.

Este algoritmo é baseado no princípio de dividir e conquistar, o que significa que a lista é dividida em duas metades a cada iteração e a busca continua apenas na metade relevante.

👩🏾‍💻 A implementação

Confira a implementação de um algoritmo de busca binária na linguagem de programação C:

int buscaBinaria(int vetor[], int tam, int valor){
    int i = 0;
    int f = tam-1;

    while(i<=f){
        int m = (i+f)/2;

        if(vetor[m]==valor) return m;

        if(vetor[m] < valor){
            i = m + 1;
        }
        else{
            f = m-1;        
        }

    }    
    return -1;
}

O algoritmo de busca binária também pode ser implementado de forma recursiva:

int buscaBinariaRecursiva(int vetor[], int inicio, int fim, int valor) {
    if (inicio > fim) return -1;

    int meio = inicio + (fim - inicio) / 2;

    if (vetor[meio] == valor) return meio;

    if (vetor[meio] < valor) {
        return buscaBinariaRecursiva(vetor, meio + 1, fim, valor);
    } else {
        return buscaBinariaRecursiva(vetor, inicio, meio - 1, valor);
    }
}