Deutsche Lernausgabe

Binäre Suche in C

Finden Sie einen Wert in einem sortierten Array durch Halbieren des Suchbereichs.

Binäre Suche benötigt ein sortiertes Array. Vergleichen Sie den Zielwert mit der Mitte: Ist er kleiner, entfällt die rechte Hälfte; ist er größer, entfällt die linke. Bei Gleichheit ist der Index gefunden.

Berechnen Sie die Mitte mit low + (high - low) / 2, um die Addition großer Indizes zu vermeiden. Schließen Sie die bereits geprüfte Mitte beim Aktualisieren der Grenzen aus. Übersteigt low den Wert high, fehlt der Zielwert.

Die iterative Variante benötigt O(log N) Zeit und O(1) Hilfsspeicher. Testen Sie Randpositionen, einen fehlenden Wert und ein einzelnes Element. Bei Duplikaten ist das Ergebnis nicht zwingend das erste Vorkommen.

Quellcode

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

Im Compiler öffnen

Erwartetes Ergebnis

Element 23 found at index 5

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.