Edición didáctica en español. El código y sus salidas conservan el original.

Búsqueda binaria en un array ordenado

Encuentra el índice de un objetivo en tiempo logarítmico o informa que no existe.

Lee N y el objetivo K, seguidos de N enteros ordenados de menor a mayor. Implementa binary_search para devolver un índice basado en cero si encuentra K, o -1 si no aparece.

Usa mid = low + (high - low) / 2 y descarta la mitad que no puede contener el objetivo. Conserva las etiquetas de salida Found at index: y Not found: -1.

Entrada

Primera línea: N y K. Segunda línea: N enteros ordenados, separados por espacios.

Salida

Found at index: <índice> o Not found: -1

Restricciones

1 <= N <= 100.000
-1.000.000.000 <= arr[i], K <= 1.000.000.000
Array ordenado en orden no decreciente.
O(log N) de tiempo y O(1) de espacio auxiliar para la búsqueda.

Pistas

Inicializa low = 0 y high = n - 1; continúa mientras low <= high.
Excluye el centro al actualizar: high = mid - 1 o low = mid + 1.

Código C

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Abrir en el compilador

Solución y explicación

Si arr[mid] coincide, devuelve mid. Si el objetivo es menor, solo puede estar a la izquierda; si es mayor, solo puede estar a la derecha.

Cada paso reduce aproximadamente a la mitad el intervalo. Cuando los límites se cruzan, el objetivo no existe. Prueba los extremos y un valor ausente.

La búsqueda cuesta O(log N), aunque leer los N valores de entrada cuesta O(N). Con duplicados, el algoritmo devuelve una aparición, no necesariamente la primera.

Código de la solución

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        // Overflow-safe midpoint calculation
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

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.