Busca binária
Última atualização
A busca binária encontra um valor-alvo em um array **ordenado** reduzindo repetidamente a janela de busca pela metade. Ela compara o elemento do meio com o alvo: se forem iguais, a busca termina; caso contrário, a metade que não pode conter o alvo é descartada e a janela encolhe para a outra metade. Cada comparação elimina metade dos elementos restantes, e é por isso que ela roda em O(log n) — buscar entre um milhão de valores ordenados exige no máximo cerca de 20 comparações.
A animação acima mostra os ponteiros lo, mid e hi e escurece a metade eliminada após cada comparação. A única pré-condição inegociável: o array já precisa estar ordenado — em dados desordenados você precisa da busca linear ou de uma ordenação primeiro (veja o merge sort). A mesma ideia de dividir ao meio move a árvore binária de busca.
Complexidade de tempo e espaço
| Caso | Complexidade | Observações |
|---|---|---|
| Melhor caso | O(1) | O elemento do meio é o alvo na primeira comparação. |
| Caso médio | O(log n) | Cada comparação reduz pela metade a janela restante. |
| Pior caso | O(log n) | A janela encolhe até um único elemento antes de acertar ou falhar. |
| Espaço | O(1) | A versão iterativa guarda apenas os índices lo, hi e mid. |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Defina lo como o primeiro índice e hi como o último índice do array ordenado. |
| 2 | Calcule o índice do meio: mid = (lo + hi) // 2. |
| 3 | Se a[mid] for igual ao alvo, retorne mid — encontrado. |
| 4 | Se a[mid] for **menor** que o alvo, o alvo só pode estar na metade direita: defina lo = mid + 1. |
| 5 | Se a[mid] for **maior** que o alvo, busque na metade esquerda: defina hi = mid - 1. |
| 6 | Repita a partir do passo 2 enquanto lo <= hi; se a janela esvaziar, o alvo não está no array. |
Exemplo resolvido
Buscando 5 em [1, 2, 3, 5, 7, 8, 9]:
| Passagem | Janela (lo..hi) | mid | a[mid] | Ação |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — alvo encontrado no índice 3. |
Uma busca sem sucesso, passo a passo
Buscar 4 no mesmo array mostra como a janela esvazia:
| Passagem | Janela (lo..hi) | mid | a[mid] | Ação |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — busque na metade esquerda, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — busque na metade direita, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo vira 3, a janela esvazia: não encontrado. |
Quando usar a busca binária
| Use quando | Evite quando |
|---|---|
| Os dados já estão ordenados (ou você os busca muitas vezes) | Os dados estão desordenados e são buscados apenas uma vez — ordenar primeiro custa O(n log n) |
| A coleção permite acesso aleatório rápido (arrays) | Você só tem acesso sequencial (listas encadeadas) |
O conjunto de dados é grande — O(log n) brilha em escala | O conjunto de dados é minúsculo — uma varredura simples é igualmente rápida e mais simples |
Código de Binary Search
Uma implementação limpa e executável de Binary Search em Python, JavaScript, Java, C++, C, Pseudocode. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Binary Search em Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Código de Binary Search em JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Código de Binary Search em Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Código de Binary Search em C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Código de Binary Search em C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Código de Binary Search em Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)Perguntas frequentes sobre busca binária
Qual é a complexidade de tempo da busca binária?
O(log n) nos casos médio e pior, porque cada comparação reduz pela metade a janela de busca restante, e O(1) no melhor caso, quando o primeiro elemento do meio é o alvo. A versão iterativa usa O(1) de espaço extra.Por que a busca binária exige um array ordenado?
O passo de dividir ao meio depende da ordem: comparar o alvo com o elemento do meio só indica qual metade descartar se tudo à esquerda do meio for menor e tudo à direita for maior. Em dados desordenados essa inferência é inválida — use a busca linear em vez disso, ou ordene primeiro.
Qual é a diferença entre busca binária e busca linear?
A busca linear percorre os elementos um a um (
O(n)) e funciona em qualquer array; a busca binária divide ao meio a janela de busca de um array ordenado (O(log n)), mas exige entrada ordenada. Para poucos itens a diferença é insignificante — em escala, a busca binária vence com folga.Quantas comparações a busca binária precisa fazer?
No máximo cerca de
log2(n) + 1: 10 comparações cobrem 1.000 elementos, 20 comparações cobrem 1.000.000. Esse crescimento logarítmico é o que a torna a busca padrão em dados ordenados.Qual é o clássico bug de overflow na busca binária?
Calcular o meio como
(lo + hi) / 2 pode estourar inteiros de tamanho fixo quando lo + hi excede o máximo do tipo. A forma segura é mid = lo + (hi - lo) / 2. Em Python isso não importa (inteiros de precisão arbitrária), mas em Java/C/C++ é um bug real e famoso.Busca binária é o mesmo que árvore binária de busca?
Elas compartilham a ideia de dividir ao meio, mas diferem na estrutura: a busca binária é um algoritmo sobre um array ordenado, enquanto a árvore binária de busca é uma estrutura de dados encadeada que mantém as chaves ordenadas para que as buscas desçam à esquerda ou à direita em cada nó.
Recursos relacionados
Mais visualizações
