Implementierung der linearen Suche in Arrays
In diesem Schritt werden Sie lernen, wie Sie einen Algorithmus für die lineare Suche in C++ implementieren. Die lineare Suche ist eine einfache Methode, um ein Element in einem Array zu finden, indem jedes Element nacheinander überprüft wird, bis das gesuchte Element gefunden oder das Ende des Arrays erreicht ist.
Öffnen Sie die WebIDE und erstellen Sie eine neue Datei namens linear_search.cpp
im Verzeichnis ~/project
:
touch ~/project/linear_search.cpp
Fügen Sie den folgenden Code zur Datei linear_search.cpp
hinzu:
#include <iostream>
int linearSearch(int arr[], int size, int target) {
// Iterieren durch jedes Element im Array
for (int i = 0; i < size; i++) {
// Überprüfen, ob das aktuelle Element mit dem Ziel übereinstimmt
if (arr[i] == target) {
return i; // Rückgabe des Indexes, wenn gefunden
}
}
return -1; // Rückgabe von -1, wenn das Ziel nicht gefunden wird
}
int main() {
// Erstellen eines Arrays mit Schülerleistungen
int scores[] = {85, 92, 78, 95, 88, 76, 90};
int size = sizeof(scores) / sizeof(scores[0]);
// Zielnote, nach der gesucht wird
int targetScore = 78;
// Durchführen der linearen Suche
int result = linearSearch(scores, size, targetScore);
// Anzeigen der Suchergebnisse
if (result!= -1) {
std::cout << "Zielnote " << targetScore
<< " an Index " << result << " gefunden" << std::endl;
} else {
std::cout << "Zielnote " << targetScore
<< " nicht im Array gefunden" << std::endl;
}
// Versuch einer anderen Suche
int missingScore = 100;
result = linearSearch(scores, size, missingScore);
if (result!= -1) {
std::cout << "Note " << missingScore
<< " an Index " << result << " gefunden" << std::endl;
} else {
std::cout << "Note " << missingScore
<< " nicht im Array gefunden" << std::endl;
}
return 0;
}
Wichtige Konzepte der linearen Suche:
- Überprüft jedes Array-Element nacheinander.
- Gibt den Index des gesuchten Elements zurück, wenn es gefunden wird.
- Gibt -1 zurück, wenn das gesuchte Element nicht im Array ist.
- Zeitkomplexität: O(n) – lineare Zeit.
- Einfach und funktioniert für unsortierte Arrays.
Kompilieren und führen Sie das Programm aus:
g++ linear_search.cpp -o linear_search
./linear_search
Beispielausgabe:
Zielnote 78 an Index 2 gefunden
Note 100 nicht im Array gefunden
Wichtige Hinweise zur Suche:
- Die lineare Suche ist einfach, aber ineffizient für große Arrays.
- Geeignet für kleine Arrays oder unsortierte Sammlungen.
- Es gibt effizientere Suchalgorithmen für sortierte Arrays.