Binäre Suche in C und C++ – Online ausführen

Was ist Binäre Suche?

Die binäre Suche verwirft nach jedem Vergleich die Hälfte des Bereichs.

Durchsuche sortierte Daten in logarithmischer Zeit.

Wichtige Punkte

Teste leere, einzelne, doppelte und sortierte Eingaben.
Trenne Korrektheit von Optimierung.
Nutze in Produktivcode bevorzugt die Standardbibliothek.

Binäre Suche visualisieren

O(log n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Codebeispiele in C und C++

C

Code ausführen →

main.c

#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}

Erwartete Ausgabe

index=4

C++

Code ausführen →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

Erwartete Ausgabe

index=4

Vergleich zwischen C und C++

Die Eingabe muss sortiert sein. C-Schleife und std::lower_bound arbeiten auf Random-Access-Bereichen in O(log n).

C

Schleifen, Pointer, Längen und Puffer sind explizit.

C++

Iteratoren und Algorithmen trennen Operation und Speicherung.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Verfolge jeden Vergleich manuell.
Teste Duplikate und Extremwerte.
Vergleiche die Laufzeit mit der Standardbibliothek.