Edição didática em português. O código e suas saídas preservam o original.

Busca binária em um array ordenado

Encontre o índice de um alvo em tempo logarítmico ou informe que ele não existe.

Leia N e o alvo K, seguidos de N inteiros em ordem não decrescente. Implemente binary_search para retornar um índice baseado em zero se encontrar K, ou -1 se ele não aparecer.

Use mid = low + (high - low) / 2 e descarte a metade que não pode conter o alvo. Preserve os rótulos de saída Found at index: e Not found: -1.

Entrada

Primeira linha: N e K. Segunda linha: N inteiros ordenados, separados por espaços.

Saída

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

Restrições

1 <= N <= 100.000
-1.000.000.000 <= arr[i], K <= 1.000.000.000
Array em ordem não decrescente.
Tempo O(log N) e espaço auxiliar O(1) para a busca.

Dicas

Inicialize low = 0 e high = n - 1; continue enquanto low <= high.
Exclua o centro ao atualizar: high = mid - 1 ou 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 no compilador

Solução e explicação

Se arr[mid] coincidir, retorne mid. Se o alvo for menor, só pode estar à esquerda; se for maior, só pode estar à direita.

Cada passo reduz aproximadamente pela metade o intervalo. Quando os limites se cruzam, o alvo não existe. Teste as extremidades e um valor ausente.

A busca custa O(log N), embora ler os N valores de entrada custe O(N). Com duplicatas, o algoritmo retorna uma ocorrência, não necessariamente a primeira.

Código da solução

#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;
}

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.