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 / 2;

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