Lineare Suche: Python, C++ Beispiel

Was ist ein Suchalgorithmus?

Ein Suchalgorithmus ist darauf ausgelegt, ein Element oder Objekt aus einer Sammlung von Elementen oder Objekten mit einer gegebenen Datenstruktur zu finden. Suchen Sie beispielsweise nach der Mindesthöhe aus einer gegebenen Liste von Höhen oder nach der höchsten Markierung aus einer Liste oder einem Array von Zahlen. Einige beliebte Suchalgorithmen sind „Lineare Suche“, „Binäre Suche“, „Sprungsuche“, „Fibonacci-Suche“ usw.

Was ist lineare Suche?

Die lineare Suche ist einer der einfachsten Suchalgorithmen. In einer gegebenen Liste oder einem Array wird nacheinander nach dem gegebenen Element gesucht. Die lineare Suche durchläuft die gesamte Liste und prüft, ob ein bestimmtes Element dem Suchelement entspricht. Sie wird auch als sequentielle Suche.

Was macht die lineare Suchfunktion?

Ein Array von ganzen Zahlen wird als „Numbers“ und eine Variable „item“ enthält die zu suchende Ganzzahl.

Jetzt kann der lineare Suchalgorithmus die folgende Ausgabe liefern:

„-1“; Dies bedeutet, dass das angegebene Element nicht im Array gefunden wird
Jede Zahl zwischen 0 und n-1; bedeutet, dass das Suchelement gefunden wurde und der Index des Elements im Array zurückgegeben wird. Hier stellt „n“ die Größe des Arrays dar.

Wie funktioniert die lineare Suche?

Nehmen wir an, es handelt sich um ein Array mit Ganzzahlen. Die Aufgabe besteht darin, eine bestimmte Zahl im Array zu finden.

Wenn sich die Zahl im Array befindet, müssen wir den Index dieser Zahl zurückgeben.
Wenn die angegebene Nummer nicht gefunden wird, wird -1 zurückgegeben.

Im Flussdiagramm ist „Daten“ das ganzzahlige Array, „N“ die Größe des Arrays und „Element“ die Zahl, nach der wir im Array suchen möchten.

Flussdiagramm für den linearen Suchalgorithmus:

Hier sind die Schritte des Flussdiagramms:

Schritt 1) Lesen Sie den Suchbegriff „Artikel“.

Schritt 2) Initiiere i=0 und index=-1

Schritt 3) Wenn ich

Schritt 4) Wenn Data[i] gleich „item“ ist, fahren Sie mit Schritt 5 fort. Andernfalls fahren Sie mit Schritt 6 fort.

Schritt 5) Index = i (Da das Element unter Indexnummer i gefunden wird). Gehen Sie zu Schritt 8.

Schritt 6) ich = ich +1.

Schritt 7) Fahren Sie mit Schritt 3 fort.

Schritt 8) Stop.

Der Einfachheit halber stellen wir ein Beispiel mit einem Array von Ganzzahlen zur Verfügung. Die lineare Suche ist auch in der Zeichenfolge, einem Array von Objekten oder einer Struktur anwendbar.

Pseudocode für sequentiellen Suchalgorithmus

function linearSearch: in →Data[], item
foundAt = -1
for i in (0 to data.length): if data[i] equals item
// item is found in the array
// returning the index
return i
// item not found in the array
// -1 means no item found, as negative index is not valid
return -1

C++ Codebeispiel Lineare Suche

#include < bits / stdc++.h >
    using namespace std;
int linearSearch(int * arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}
int main() {
    int array[] = {
        1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
    };
    int n = sizeof(array) / sizeof(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Ausgang:

Enter a number to search: -10
-10 is found at index 14

Python Codebeispiel Lineare Suche

def linearSearch(data, item):
    for i in range(len(data)):
    if data[i] == item:
    return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else :
    print("{} was not found".format(item))

Ausgang:

Enter a number to search: -10
-10 is found at index 14

Komplexitätsanalyse des linearen Suchalgorithmus

Im Allgemeinen bezeichnet die Zeitkomplexität die CPU-Zeit, die zum Ausführen einer bestimmten Aufgabe benötigt wird. Beim linearen Suchalgorithmus besteht die Aufgabe darin, den Suchschlüssel aus dem Element des Arrays zu finden.

Es gibt drei Arten von Zeitkomplexitäten:

Worst Case Scenario
besten Case Szenario
Durchschnittliches Fallszenario

Zeitliche Komplexität der linearen Suche im Worst-Case-Szenario:

Nehmen wir an, wir müssen eine lineare Suche in einem Array mit der Größe „n“ durchführen. Wir können den Suchbegriff zwischen Index 0 und n-1 finden. Im schlimmsten Fall versucht der Algorithmus, alle Elemente aus dem Array mit dem Suchelement abzugleichen.

In diesem Fall beträgt die Komplexität im schlimmsten Fall O(n). Hier steht die „O“-Notation für die Komplexitätsfunktion.

Zeitliche Komplexität der linearen Suche im besten Fall:

Nehmen wir an, wir suchen nach einem Element, das sich an der ersten Position im Array befindet. In diesem Szenario sucht der lineare Suchalgorithmus nicht nach allen n Elementen im Array. Die Komplexität beträgt also O(1). Dies bedeutet konstante Zeit.

Zeitliche Komplexität der linearen Suche im durchschnittlichen Szenario:

Wenn ein Element am mittleren Index des Arrays gefunden wird, kann man sagen, dass die durchschnittliche Komplexität bei der linearen Suche O(N) beträgt, wobei N die Länge des Arrays darstellt.

Die räumliche Komplexität des linearen Suchalgorithmus

Die Speicherkomplexität für die lineare Suche beträgt immer O(N), da wir in der linearen Suchfunktion keine temporären Variablen speichern oder verwenden müssen.

So verbessern Sie den linearen Suchalgorithmus

Die Suche kann während des gesamten Lebenszyklus des Programms mehrmals durchgeführt werden. Es ist auch möglich, dass wir den linearen Suchalgorithmus ausführen und mehrmals nach einem bestimmten Schlüssel suchen. Wir können die Funktion „Binärer Suchalgorithmus” wenn das Array ein sortiertes Array ist.

Angenommen, das Array besteht aus 10 Zahlen und das Zielelement befindet sich am 5000. Index. Der Algorithmus wird also versuchen, 5000 Elemente zu vergleichen. Vergleiche sind jedoch CPU-intensive Aufgaben. Um den linearen Suchalgorithmus zu optimieren, haben wir zwei Möglichkeiten.

Transposition
Nach vorne verschieben

Umsetzung:

Bei dieser Methode tauschen wir das Suchelement mit seinem vorherigen Element im Array aus. Nehmen wir beispielsweise an, Sie haben ein Array wie das folgende:

Daten[] = {1,5,9,8,7,3,4,11}

Nun wollen wir 4. Schritte der Transposition suchen:

Schritt 1) „4“ steht bei Index 6. Es waren sechs Vergleiche erforderlich.

Schritt 2) Tauschen Sie Daten[6] und Daten[5] aus. Dann sieht das Datenarray so aus:

Daten[] = {1,5,9,8,7,4,3,11}

Schritt 3) Suchen Sie erneut nach 4. Gefunden bei Index 5. Diesmal waren fünf Vergleiche erforderlich.

Schritt 4) Tauschen Sie Daten [5] und Daten[4] aus. Dann sieht das Datenarray so aus:

Daten [] = {1,5,9,8,4,7,3,11}

Wie Sie nun bemerken, verringert sich der Index umso mehr, je häufiger nach einem Schlüssel gesucht wird. Dadurch verringert sich die Anzahl der Vergleiche.

Nach vorne verschieben:

Bei dieser Methode tauschen wir das Suchelement im 0. Index aus. Denn wenn es erneut gesucht wird, können wir es zum Zeitpunkt O(1) finden.

Anwendung des linearen Suchalgorithmus

Hier sind einige lineare Suchanwendungen, die wir verwenden können.

Bei kleinen Arrays oder nur wenigen Elementen in der Liste ist es einfacher, die lineare Suche zu verwenden.
Die lineare Suchmethode kann einzeln oder einzeln verwendet werden mehrdimensionale Arrays oder andere Datenstrukturen.
Im Allgemeinen ist die lineare Suche einfach und effizient, um eine Suche in „ungeordneten“ Daten durchzuführen. Wir können problemlos einzelne Daten aus der angegebenen ungeordneten Liste abrufen.