Deutsche Lernausgabe

Binäre Suche in einem C-Array

Suchen Sie einen Wert in einem sortierten Array, indem Sie den Suchbereich wiederholt halbieren.

Lesen Sie N, den Zielwert K und ein nicht absteigend sortiertes Array. Geben Sie den bei null beginnenden Index eines Vorkommens von K zurück oder -1, falls der Wert fehlt.

Vergleichen Sie den Zielwert mit dem mittleren Element und verwerfen Sie die Hälfte, die ihn nicht enthalten kann. Bei Duplikaten ist jedes Vorkommen zulässig; die Aufgabe verlangt nicht zwingend das erste.

Eingabe

N und K, danach N nicht absteigend sortierte Ganzzahlen.

Ausgabe

Found at index: <Index>, wenn das Ziel vorkommt, sonst Not found: -1.

Vorgaben

1 ≤ N ≤ 100000; Werte zwischen -10⁹ und 10⁹.
Suche in O(log N) Zeit mit O(1) Zusatzspeicher.

Hinweise

Beginnen Sie mit low = 0 und high = N - 1; wiederholen Sie, solange low <= high gilt.
Berechnen Sie mid = low + (high - low) / 2, um die direkte Addition der Grenzen zu vermeiden.
Setzen Sie nach einem ungleichen Vergleich high = mid - 1 oder low = mid + 1.

Quellcode

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

Im Compiler öffnen

Erklärung der Lösung

Bewahren Sie die Invariante: Falls das Ziel im verbleibenden Bereich vorkommt, liegt sein Index zwischen low und high einschließlich. Gleichheit beendet die Suche sofort.

Sobald low größer als high ist, bleibt keine mögliche Position: Geben Sie -1 zurück. Die Suche ist logarithmisch, doch das Einlesen der N Werte benötigt weiterhin O(N) Zeit.

Lösungscode

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

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.