Lineare Suche
Die lineare Suche prüft Elemente bis zum Treffer oder Ende.
Was ist Lineare Suche?
Die lineare Suche prüft Elemente bis zum Treffer oder Ende.
Finde ein Ziel in unsortierten Daten.
Wichtige Punkte
- Teste leere, einzelne, doppelte und sortierte Eingaben.
- Trenne Korrektheit von Optimierung.
- Nutze in Produktivcode bevorzugt die Standardbibliothek.
Lineare Suche visualisieren
O(n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Codebeispiele in C und C++
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));
}
index=3main.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';
}
index=3Vergleich zwischen C und C++
Beide Varianten benötigen im ungünstigsten Fall O(n). C nutzt -1 als fehlenden Index; C++ liefert einen Iterator und vergleicht mit end.
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.