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

Lineare Suche in C und C++

In dieser Lektion findest du mit der linearen Suche die Position eines Werts in einem unsortierten Array.

Einführung

Die lineare Suche prüft die Elemente vom Anfang des Arrays an nacheinander, bis sie den gesuchten Wert findet oder das Ende erreicht. Sie ist der einfachste Suchalgorithmus und funktioniert auch mit unsortierten Daten.

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.

Lineare Suche in C und C++ visualisieren

O(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 find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}
Ergebnis der Ausführung
index=3
C++
Code ausführen →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Ergebnis der Ausführung
index=3

C und C++ im Vergleich

Beide Versionen haben im schlechtesten Fall die Komplexität O(n). Die Funktion find in C gibt einen vorzeichenbehafteten int-Index zurück und kann deshalb -1 verwenden, um anzuzeigen, dass nichts gefunden wurde. Die C++-Version verwendet std::find, das einen Iterator zurückgibt; ist er gleich values.end(), ist der Wert nicht im Array.

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