A Busca Binária

Introdução

A busca binária (ou pesquisa binária) é um algoritmo de busca para vetores ordenados (arrays). A sua principal vantagem é que a busca é realizada em tempo logarítmico, sendo mais rápida do que a busca linear.

O objetivo da postagem é apresentar o algoritmo da busca binária e algumas implementações.

Como Funciona a Busca Binária

Primeiramente, para que a busca binária funcione, é necessário que o vetor onde a busca será realizada esteja ordenado.

Ao procurar um elemento, verificamos se ele encontra-se no meio do vetor. Se ele não estiver no meio, então verificamos se o elemento que estamos procurando é maior ou menor que o elemento do meio.

Se for maior, então fazemos a busca no subvetor à direita do elemento do meio e desprezamos o que está à esquerda. Lembre-se que como o vetor está ordenado, então, neste caso, todos os elementos à esquerda serão menores que o elemento que estamos buscando, portanto ele não estará lá.

Por outro lado, se o elemento procurado for menor que o do meio, então realizamos o mesmo procedimento, porém iremos fazer a busca no subvetor à esquerda e desprezaremos os elementos à direita, pois estes serão maiores que o elemento em questão.

A busca encerra quando o elemento é encontrado ou quando o último subvetor não contém o elemento desejado, isto ele não está no vetor.

A cada tentativa de pesquisa, o nosso espaço de busca é reduzido pela metade. Este é o "segredo" da busca binária, que só é possível justamente porque o vetor está ordenado.

A seguir, apresento o algoritmo da busca, que implementa (recursivamente) a lógica apresentada nos parágrafos anteriores utilizando pseudocódigo.

BuscaBinaria (A, inicio, fim, x)
  se(inicio ≤ fim)
    m ← (inicio + fim)/2 //calcula o meio
    se(x = A[m])
      retorne m //elemento encontrado
    senão
      se(x > A[m])
        //faz a busca no subvetor à direita
        retorne BuscaBinaria(A, m + 1, fim, x)
      senão
        //faz a busca no subvetor à esquerda
        retorne BuscaBinaria(A, inicio, m - 1, x)
      fim_se
    fim_se
  senão
    retorne -1 //elemento não encontrado
  fim_se
fim

Há também a versão iterativa:

BuscaBinaria (A, x)
  inicio ← 0
  fim ← A.tamanho – 1
    enquanto(inicio ≤ fim)
      m ← (inicio + fim)/2 //calcula o meio
        se(x = A[m])
          retorne m //elemento encontrado
        senão
          se(x > A[m])
            //faz a busca no subvetor à direita
            inicio ← m + 1
          senão
            //faz a busca no subvetor à esquerda
            fim ← m - 1
          fim_se
        fim_se
      fim_enquanto
      retorne -1 //elemento não encontrado
fim

Como exemplo, vamos ilustrar as etapas para localizar o número 20 no vetor a seguir:

Inicialmente, temos inicio = 0 e fim = 7.

Calculamos o meio: m = (0 + 7)/2 = 3.

A[3] = 9 ≠ 20. Como 20 > 9, então inicio = m + 1 = 3 + 1 = 4. Como inicio ≤ fim (4 ≤ 7), então continuamos.

Calculamos o meio: m = (4+7)/2 = 5.

A[5] = 27 ≠ 20. Como 20 < 27, então fim = m - 1 = 5 - 1 = 4. Como inicio ≤ fim (4 ≤ 4), então continuamos.

Calculamos o meio: m = (4 + 4)/2 = 4.

A[4] = 20. Retornamos 4. Busca encerrada.

Análise do Algoritmo

O melhor caso da busca binária ocorre quando o elemento que procuramos está no meio do vetor. Dessa forma, haverá apenar uma chamada recursiva/iteração. Portanto, o algoritmo tem complexidade constante: Θ(1) ou O(1).

O pior caso ocorre quando o elemento que buscamos não está no vetor. Tanto a versão iterativa, como a versão recursiva possuem complexidade de O(log n).

No caso da versão recursiva, a equação de recorrência do pior caso é dada por:

A equação pode se resolvida pelo Teorema Meste produzindo T(n) = Θ(log n), que implica que T(n) = O(log n). A mesma complexidade pode ser obtida também via Método de Akra-Bazzi.

O caso médio também é O(log n) e a demonstração pode ser encontrada no seguinte link (Computer Science Stack Exchange, em inglês): Proving that the average case complexity of binary search is O(log n).

Códigos

A seguir apresento as duas versões da busca binária (iterativa e recursiva) em C e em Java. Ressalto que a biblioteca padrão de ambas as linguagens já possuem o algoritmo implementado.

Se preferir, você também pode fazer o download dos códigos nos links a seguir:

• Busca Binária no Google Drive (Java e C)
• Busca Binária no GitHub

Código em C

/*
 * Henrique Felipe (GitHub: HenriqueIni)
 * https://www.blogcyberini.com/
 *
 * Código sob licença MIT
 */
#include <stdio.h>
#include <stdlib.h>
 
/*
 * Tenta encontra o elemento no array especificado (iterativamente). 
 * Complexidade no tempo: O(log n) 
 */
int binarySearchIterative(int a[], int size, int key) {
    int begin = 0;
    int end = size - 1;
    while (begin <= end) {
        int middle = (begin + end) / 2; //calcula o meio
        if (key == a[middle]) {
            //o elemento foi encontrado
            return middle;
        } else {
            if (key > a[middle]) {
                //a busca continuará no subarray à direira
                begin = middle + 1;
            } else {
                //a busca continuará no subarray à esquerda
                end = middle - 1;
            }
        }
    }
    //o elemento não está no array
    return -1;
}
/*
 * Tenta encontra o elemento no array especificado (recursivamente). 
 * Complexidade no tempo: O(log n) 
 */
int binarySearchRecursive(int a[], int begin, int end, int key) {
    if (begin <= end) {                    
        int middle = (begin + end) / 2; //calcula o meio
        if (key == a[middle]) {
            //o elemento foi encontrado
            return middle;
        } else {
            if (key > a[middle]) {
                //a busca continuará no subarray à direira
                return binarySearchRecursive(a, middle + 1, end, key);
            } else {
                //a busca continuará no subarray à esquerda
                return binarySearchRecursive(a, begin, middle - 1, key);
            }
        }
    } else {
        //o elemento não está no array
        return -1;
    }
}
/*
 * Função de testes
 */
int main() {
    int test[] = {1, 3, 4, 55, 104, 222, 229, 300};
    int n = sizeof(test)/sizeof(int);
    int key = 55;
    printf("%d\n%d\n", binarySearchRecursive(test, 0, n - 1, key), binarySearchIterative(test, n, key));
    return 0;
}

Código em Java

/*
 * Henrique Felipe (GitHub: HenriqueIni)
 * https://www.blogcyberini.com/
 * Código sob licença MIT
 */
public class BinarySearch {
     //Tenta encontra o elemento no array especificado (iterativamente).
     //Complexidade no tempo: O(log n).      
    public static int binarySearchIterative(int[] a, int key) {
        int begin = 0;
        int end = a.length - 1;
        while (begin <= end) {
            //calcula o meio
            int middle = (begin + end) / 2;
            if (key == a[middle]) {
                //o elemento foi encontrado
                return middle;
            } else if (key > a[middle]) {
                //a busca continuará no subarray à direira
                begin = middle + 1;
            } else {
                //a busca continuará no subarray à esquerda
                end = middle - 1;
            }
        }
        //o elemento não está no array
        return -1;
    }
 
    //Tenta encontra o elemento no array especificado (recursivamente).
    //Complexidade no tempo: O(log n).      
    public static int binarySearchRecursive(int[] a, int begin, int end, int key) {
        if (begin <= end) {
            //calcula o meio
            int middle = (begin + end) / 2;
            if (key == a[middle]) {
                //o elemento foi encontrado
                return middle;
            } else if (key > a[middle]) {
                //a busca continuará no subarray à direira
                return binarySearchRecursive(a, middle + 1, end, key);
            } else {
                //a busca continuará no subarray à esquerda
                return binarySearchRecursive(a, begin, middle - 1, key);
            }
        } else {
            //o elemento não está no array
            return -1;
        }
    }
    //Código de testes
    public static void main(String[] args) {
        int[] test = {1, 3, 4, 55, 104, 222, 229, 300};
        System.out.println(binarySearchRecursive(test, 0, test.length - 1, 55));
        System.out.println(binarySearchIterative(test, 55));
    }
}

Curiosidade

Uma das questões dissertativas do ENADE 2014 de Sistemas de Informação solicitava que o aluno desenvolvesse um algoritmo de busca binária:

Disponibilizei a prova no Google Drive: ENADE 2014 (Sistemas de Informação).

Referências

• [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
• [2] FEOFILOFF P. Busca em vetor ordenado. Acesso em 5 de setembro de 2017.