Nicht einmal ein einziger Tag vergeht, wenn wir in unserem täglichen Leben nicht nach etwas suchen müssen, Autoschlüssel, Bücher, Stift, mobiles Ladegerät und was nicht. Das Gleiche gilt für das Leben eines Computers, in dem so viele Daten gespeichert sind, dass der Computer jedes Mal, wenn ein Benutzer nach Daten fragt, den Speicher durchsuchen muss, um nach den Daten zu suchen und sie dem Benutzer zur Verfügung zu stellen. Und der Computer verfügt über eigene Techniken, um den Speicher schnell zu durchsuchen, worüber Sie in unserer Tutorial-Serie zum Betriebssystem mehr erfahren können.
Was ist, wenn Sie ein Programm schreiben müssen, um eine bestimmte Zahl in einem Array zu suchen? Wie werden Sie es tun?
Um ein Element in einem bestimmten Array zu suchen, stehen zwei gängige Algorithmen zur Verfügung:
- Lineare Suche
- Binäre Suche
Lineare Suche
Die lineare Suche ist ein sehr einfacher und einfacher Suchalgorithmus. Bei der linearen Suche suchen wir ein Element oder einen Wert in einem bestimmten Array, indem wir das Array von Anfang an durchlaufen, bis das gewünschte Element oder der gewünschte Wert gefunden wird.
Es vergleicht das zu durchsuchende Element mit allen im Array vorhandenen Elementen und gibt, wenn das Element erfolgreich abgeglichen wurde, den Index des Elements im Array zurück, andernfalls -1 .
Die lineare Suche wird auf unsortierte oder ungeordnete Listen angewendet, wenn weniger Elemente in einer Liste vorhanden sind.
Merkmale des linearen Suchalgorithmus
- Es wird für unsortierte und ungeordnete kleine Liste von Elementen verwendet.
- Es hat eine Zeitkomplexität von O(n), was bedeutet, dass die Zeit linear von der Anzahl der Elemente abhängt, was nicht schlecht, aber auch nicht so gut ist.
- Es hat eine sehr einfache Implementierung.
Wir werden den linearen Suchalgorithmus im nächsten Tutorial implementieren.
Binäre Suche
Binäre Suche wird mit sortiertem Array oder Liste verwendet. Bei der binären Suche führen wir die folgenden Schritte aus:
- Wir beginnen mit dem Vergleich des zu durchsuchenden Elements mit dem Element in der Mitte der Liste / des Arrays.
- Wenn wir eine Übereinstimmung erhalten, geben wir den Index des mittleren Elements zurück.
- Wenn wir keine Übereinstimmung erhalten, prüfen wir, ob das zu durchsuchende Element kleiner oder größer als das mittlere Element ist.
- Wenn das zu durchsuchende Element / die zu durchsuchende Nummer einen größeren Wert als die mittlere Nummer hat, wählen wir die Elemente auf der rechten Seite des mittleren Elements aus (da die Liste / das Array sortiert ist, haben wir auf der rechten Seite alle Zahlen größer als die mittlere Nummer) und beginnen erneut mit dem Schritt 1.
- Wenn das zu durchsuchende Element / die zu durchsuchende Nummer einen geringeren Wert als die mittlere Nummer hat, wählen wir die Elemente auf der linken Seite des mittleren Elements aus und beginnen erneut mit dem Schritt 1.
Die binäre Suche ist nützlich, wenn sich eine große Anzahl von Elementen in einem Array befindet und diese sortiert sind.
Eine notwendige Bedingung für die binäre Suche ist also, dass die Liste / das Array sortiert werden sollte.
Funktionen der binären Suche
- Es ist großartig, große sortierte Arrays zu durchsuchen.
- Es hat eine Zeitkomplexität von O(log n), was eine sehr gute Zeitkomplexität ist. Wir werden dies im Tutorial zur binären Suche ausführlich besprechen.
- Es hat eine einfache Implementierung.