A Busca Binária

Por
|  

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:

Um vetor

Inicialmente, temos inicio = 0 e fim = 7.

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

Um vetor

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

Um vetor

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

Um vetor

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

Um vetor

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

Um vetor

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:

Equação de recorrência da busca binária

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:

Google Drive: Busca Binária (Códigos).

GitHub: BinarySearch (BlogCyberiniCodes).

Código em C

            /*
             * Henrique Felipe (GitHub: HenriqueIni)
             * https://blogcyberini.blogspot.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://blogcyberini.blogspot.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:

Questão do ENADE 2014 sobre busca binária

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

Referências

CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.

FEOFILOFF P. Busca em vetor ordenado. Disponível em <https://www.ime.usp.br/~pf/algoritmos/aulas/bubi.html>. Acesso em 5 de setembro de 2017.

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário