Edição didática em português. O código e suas saídas preservam o original.
Busca binária em C
Encontre um valor em um array ordenado reduzindo o intervalo de busca pela metade.
A busca binária exige um array ordenado. Compare o alvo com o elemento central: se for menor, descarte a metade direita; se for maior, descarte a metade esquerda. Se coincidir, retorne o índice.
Calcule o centro como low + (high - low) / 2 para evitar somar dois índices grandes. Atualize os limites excluindo o centro já verificado e termine quando low ultrapassar high. Retorne um resultado explícito para um valor ausente.
A versão iterativa usa tempo O(log N) e espaço auxiliar O(1). Teste o primeiro e o último elemento, um valor ausente e um array de um elemento. Com duplicatas, esta versão não promete retornar a primeira ocorrência.
Código C
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
// Prevent (low + high) integer overflow
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1; // Target not found
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, n, target);
if (result != -1)
printf("Element %d found at index %d\n", target, result);
else
printf("Element %d not present\n", target);
return 0;
}Saída esperada
Element 23 found at index 5
Perguntas frequentes
Por que o código e a saída continuam em inglês?
Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.