Edición didáctica en español. El código y sus salidas conservan el original.
Búsqueda binaria en C
Encuentra un valor en un array ordenado reduciendo el intervalo de búsqueda a la mitad.
La búsqueda binaria exige un array ordenado. Compara el objetivo con el elemento central: si es menor, descarta la mitad derecha; si es mayor, descarta la mitad izquierda. Si coincide, devuelve el índice.
Calcula el centro como low + (high - low) / 2 para evitar sumar dos índices grandes. Actualiza los límites excluyendo el centro ya comprobado y termina cuando low supera high. Devuelve un resultado explícito para un valor ausente.
La versión iterativa usa O(log N) de tiempo y O(1) de espacio auxiliar. Prueba el primer y último elemento, un valor ausente y un array de un elemento. Con duplicados, esta versión no promete devolver la primera aparición.
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;
}Salida esperada
Element 23 found at index 5
Preguntas frecuentes
¿Por qué el código y la salida siguen en inglés?
Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.