CodeUtility
Mach dir das Coderleben leicht!
C/C++-Algorithmen

Binäre Suche in C und C++

In dieser Lektion suchst du in einem sortierten Array in O(log n) Zeit, mit einer selbst geschriebenen Schleife in C und mit std::lower_bound in C++.

Einführung

Die binäre Suche vergleicht den gesuchten Wert mit dem mittleren Element des Suchbereichs und verwirft die Hälfte, die ihn nicht enthalten kann. Wiederholt man das, schrumpft der Suchbereich sehr schnell, die Eingabedaten müssen aber vorher sortiert sein.

Wichtige Punkte

  • Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
  • Zuerst richtig machen, dann optimieren.
  • Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.

Binäre Suche in C und C++ 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));
}
Ergebnis der Ausführung
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';
}
Ergebnis der Ausführung
index=4

C und C++ im Vergleich

In der C-Version wird die Mitte mit low + (high - low) / 2 statt mit (low + high) / 2 berechnet, um bei sehr großen Indizes einen Überlauf zu vermeiden. Nach jedem Vergleich wird low oder high in die verbleibende Hälfte verschoben. Die C++-Version verwendet std::lower_bound, um die erste Position zu finden, die nicht kleiner als der gesuchte Wert ist. Beide haben die Komplexität O(log n).

C

Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.

C++

Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

  • Spiele jeden Vergleich auf Papier durch.
  • Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
  • Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges