Lineare Suche: Python, C++ Beispiel

Was ist ein Suchalgorithmus?

Ein Suchalgorithmus dient dazu, ein Element oder Objekt mit einer bestimmten Datenstruktur aus einer Menge von Elementen oder Objekten zu finden. Beispielsweise kann man die kleinste Höhe aus einer Liste von Höhen oder den höchsten Wert aus einer Liste oder einem Array von Zahlen suchen. Zu den gängigen Suchalgorithmen gehören die lineare Suche, die binäre Suche, die Sprungsuche und die Fibonacci-Suche.

Was ist lineare Suche?

Lineare Suche ist einer der einfachsten Suchalgorithmen. Er durchsucht eine gegebene Liste oder ein Array nacheinander nach dem gesuchten Element. Die lineare Suche iteriert über die gesamte Liste und prüft, ob ein bestimmtes Element mit dem gesuchten Element übereinstimmt. Sie wird auch als … bezeichnet. 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“ bedeutet, dass das angegebene Element im Array nicht gefunden wurde.
• 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?

Angenommen, wir haben ein Array, das ganze Zahlen enthält. Die Aufgabe besteht darin, eine bestimmte Zahl in diesem 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) Initialisiere 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 sich das Element an Index i befindet). Fahre mit Schritt 8 fort.

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.

Spitzname Code für den sequenziellen Suchalgorithmus

Der folgende Pseudocode veranschaulicht die Logik der oben beschriebenen linearen Suche. Er durchläuft das Array vom ersten Index an und gibt bei einer Übereinstimmung die Position zurück, andernfalls -1.

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 a negative index is not valid
    return -1

C++ Code Beispiel einer linearen Suche

Hier ist eine vollständige C++ Programm, das die sequentielle Suche implementiert und den Index des gesuchten Wertes ausgibt.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Beispiel einer linearen Suche

Die gleiche Logik in Python verwendet eine einzige Schleife über die Listenindizes und gibt die Position des übereinstimmenden Elements zurück.

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 den Zeitaufwand der CPU für die Ausführung einer bestimmten Aufgabe. Beim linearen Suchalgorithmus besteht die Aufgabe darin, den Suchschlüssel aus den Elementen 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:

Angenommen, wir müssen eine lineare Suche in einem Array der Größe „n“ durchführen. Wir können das gesuchte Element zwischen Index 0 und n-1 finden. Im ungünstigsten Fall versucht der Algorithmus, alle Elemente des Arrays mit dem gesuchten Element abzugleichen.

In diesem Fall beträgt die Worst-Case-Komplexität O(n). Hierbei bezeichnet „O“ – in der O-Notation – die Komplexitätsfunktion.

Zeitliche Komplexität der linearen Suche im besten Fall:

Angenommen, wir suchen ein Element an der ersten Position eines Arrays. In diesem Fall durchsucht der lineare Suchalgorithmus nicht alle n Elemente des Arrays. Die Komplexität beträgt daher O(1), was einer konstanten Laufzeit entspricht.

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 Speicherkomplexität des linearen Suchalgorithmus:

Die Speicherkomplexität der linearen Suche beträgt immer O(N), da in der linearen Suchfunktion keine temporären Variablen gespeichert oder verwendet werden müssen.

So verbessern Sie den linearen Suchalgorithmus

Die Suche kann während des gesamten Programmlebenszyklus 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 „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 vertauschen wir das Suchelement mit seinem vorherigen Element im Array. 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) Vertausche data[5] und data[4]. Dann sieht das Datenarray folgendermaßen aus:

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

Wie Sie vielleicht bemerkt haben, verringert sich der Index umso mehr, je häufiger ein Schlüssel gesucht wird. Dadurch sinkt auch die Anzahl der Vergleiche.

Nach vorne verschieben:

Bei dieser Methode wird das Suchelement an den Index 0 verschoben. Denn wenn erneut danach gesucht wird, kann es in konstanter Zeit (O(1)) gefunden werden.

Anwendung des linearen Suchalgorithmus

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

• Bei kleinen Arrays oder Listen mit nur wenigen Elementen ist die lineare Suche einfacher anzuwenden.
• 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.

Häufig gestellte Fragen