Busca Binária

O que é a Busca Binária?

A Busca Binária é um algoritmo de divisão e conquista que encontra a posição de um valor alvo dentro de um array estritamente ordenado.

A Filosofia do "Espaço de Busca"

Em computação, o tempo é o recurso mais caro. Quando buscamos algo de forma sequencial, o esforço é O(n). Se o $n$ (número de dados) dobra, o tempo dobra. Na busca binária, o esforço é Logarítmico O(log n).

Análise → Você precisa fazer uma busca em uma lista com 1 bilhão de itens:

• A busca linear pode levar 1 bilhão de operações.
• A busca binária resolve em no máximo 30 operações.

Por que ela é tão superior? Porque ela não "procura" o elemento; ela descarta o que não interessa. Ela trabalha sobre a certeza de que, em um conjunto ordenado, se o valor no meio é maior que o seu alvo, todos os valores à direita também serão, por definição, inúteis para você.

Como Funciona: O Mecanismo Interno

O funcionamento baseia-se em manter três controladores que delimitam a região de interesse:

1. Low (Baixo): O índice do início do segmento atual.
2. High (Alto): O índice do fim do segmento atual.
3. Mid (Meio): O ponto de inspeção.

A cada iteração, o algoritmo "corta o mundo ao meio". Se o alvo não está no Mid, o Low ou o High são ajustados para ignorar a metade onde o alvo certamente não está. O espaço de busca colapsa geometricamente até que o item seja encontrado ou os ponteiros se cruzem (indicando que o item não existe).

Aplicação e Simulação Real

Vamos aplicar isso em um cenário de Dicionário de IDs. Suponha o array ordenado: [102, 250, 480, 510, 600, 750, 900] e queremos o ID 750.

Estado Inicial: Low=0, High=6

• Calculamos Mid = 3 (valor 510).
• Comparação: 750 > 510? Sim.
• Decisão: Mover Low para Mid + 1 (índice 4). Metade do array foi descartada aqui.

Estado 2: Low=4, High=6

• Calculamos Mid = 5 (valor 750).
• Comparação: 750 == 750? Sim!
• Resultado: Sucesso em 2 passos

Implementação em C Puro

O código mostra a implementação na linguagem C, de maneira objetiva:

                
                    #include <stdio.h>        

                    // Protótipo da função para clareza
                    int binarySearch(int arr[], int size, int target) {
                        int left = 0;
                        int right = size - 1;

                        while (left <= right) {
                            // Uso de (right - left) evita overflow de inteiros
                            int mid = left + (right - left) / 2;

                            // Caso 1: Encontrou o alvo
                            if (arr[mid] == target) {
                                return mid;
                            }

                            // Caso 2: O alvo está na metade superior
                            if (arr[mid] < target) {
                                left = mid + 1;
                            } 
                            // Caso 3: O alvo está na metade inferior
                            else {
                                right = mid - 1;
                            }
                        }

                        // Se o loop terminar, o elemento não existe
                        return -1;
                    }

                    int main() {
                        int v[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
                        int n = sizeof(v) / sizeof(v[0]);
                        int alvo = 70;

                        int idx = binarySearch(v, n, alvo);

                        (idx != -1) ? printf("Encontrado na posicao %d\n", idx) 
                                    : printf("Nao encontrado\n");

                        return 0;
                    }
                
            

Complexidade

A Busca Binária opera em tempo O(log n). Veja como isso se traduz em performance real:

Perguntas para Fixação