Lineare Suche vs. binäre Suche: Unterschied zwischen linearer Suche und binärer Suche

Einführung

Kontinuierliche Speicherzuweisung in Programmiersprachen bietet eine flexible Implementierung zum Speichern mehrerer Datenpunkte. Dies kann auf dem Höhepunkt genutzt werden, wenn wir die Daten trennen und alle ähnlichen Daten in einer zusammenhängenden Datenstruktur wie einem Array, einer Liste usw. zusammenführen möchten.

Kontinuierliche Speicherzuweisung hat viele Implementierungen in realen Anwendungen wie einem Betriebssystem in Computern, Datenbankverwaltungssystemen usw. Diese Datenstruktur wird als flexibel angesehen, da das Hinzufügen eines neuen Datenpunkts zu einem Array nur eine einzige Zeiteinheit erfordert, dh; O(1).

Das Problem tritt jedoch auf, wenn wir einen bestimmten Eintrag betrachten oder nach einem bestimmten Eintrag suchen möchten, da alle realen Anwendungen auf die Datenzugriffsbefehle angewiesen sind. Und diese Aufgabe muss schnell genug sein, um der Geschwindigkeit des Prozessors und des Speichers gerecht zu werden.

Es gibt verschiedene Suchalgorithmen, die basierend auf der Anzahl der Vergleiche unterteilt sind, die wir zum Durchsuchen des Elements durchführen.

Wenn wir jeden Datenpunkt im Array vergleichen, um ein Element zu suchen, wird dies als sequentielle Suche betrachtet. Wenn wir jedoch nur wenige Elemente vergleichen, indem wir einige der Vergleiche überspringen, wird dies als Intervallsuche betrachtet. Aber wir brauchen ein Array in sortierter Reihenfolge (aufsteigende oder absteigende Reihenfolge), um eine Intervallsuche darauf durchzuführen.

Die Zeitkomplexität der sequentiellen Suche ist linear O(n), und die Zeitkomplexität der binären Suche (ein Beispiel einer Intervallsuche) ist O(log n). Außerdem gibt es andere Suchalgorithmen wie exponentielle Suche, Sprungsuche usw.

Aber lineare Suche und binäre Suche werden meistens verwendet, wobei die lineare Suche für zufällige oder unsortierte Daten und die binäre Suche für sortierte und geordnete Daten ist. Hashing ist ein spezieller Suchalgorithmus, bei dem die Zeitkomplexität des Zugriffs auf einen Datenpunkt O(1) beträgt.

Lassen Sie uns zuerst die Algorithmen der linearen Suche und der binären Suche durchgehen und dann die Unterschiede zwischen der linearen Suche und der binären Suche vergleichen.

Lineare Suche

Wie bereits erwähnt, vergleicht der lineare Suchalgorithmus jedes Element im Array, und hier ist der Code dafür.

Lassen Sie uns den Code durchgehen.

Wir haben eine linear_search-Funktion deklariert, die ein Array und einen Integer-Schlüssel als Parameter erwartet. Jetzt müssen wir alle Elemente durchlaufen und vergleichen, ob sie mit unserem Suchschlüssel übereinstimmen, also haben wir eine for-Schleife geschrieben, die das Array durchläuft, und darin gibt es eine if-Schleife, die prüft, ob die Zahl an dieser Position übereinstimmt mit dem Suchschlüssel oder nicht. Wenn wir eine Übereinstimmung finden, geben wir die Position zurück. Wenn das Array kein solches Element enthält, geben wir am Ende der Funktion -1 zurück.

Beachten Sie, dass wir bei mehreren Vorkommen derselben Zahl die Position ihres ersten Vorkommens zurückgeben.

Kommen wir zur Hauptmethode, wir haben ein Integer-Array deklariert und initialisiert. Dann initialisieren wir den zu suchenden Schlüssel. Hier codieren wir das Array und den Schlüssel fest, aber Sie können es in eine Benutzereingabe ändern. Nachdem wir nun die Liste der Elemente und den zu durchsuchenden Schlüssel erhalten haben, wird die lineare Suchmethode aufgerufen und der zurückgegebene Index notiert. Später überprüfen wir den zurückgegebenen Wert und drucken den Index, wenn der Schlüssel vorhanden ist, andernfalls wird der Druckschlüssel nicht gefunden.

Binäre Suche

Die binäre Suche ist optimierter als die lineare Suche, aber das Array muss sortiert werden, um die binäre Suche anzuwenden. Und hier ist der Code dafür.

Lassen Sie uns den Code durchgehen.

Wir haben eine Methode binary_search deklariert, die als Parameter ein sortiertes Integer-Array und einen Integer-Schlüssel erwartet. Wir initialisieren die Variablen low, high, mid. Hier sind Low, High Zeiger, wobei Low am Anfang bei 0 Index und High bei n Index sein wird. Wie funktioniert die binäre Suche?

Zuerst berechnen wir die Mitte von Tief und Hoch. Wir können die Mitte als (niedrig + hoch)/2 berechnen, aber manchmal kann hoch eine große Zahl sein, und das Hinzufügen von niedrig zum Hoch kann zu einem ganzzahligen Überlauf führen. Die Berechnung von Mid als Low + (High-Low) / 2 wäre also ein optimaler Weg.

Wir vergleichen das Element in der Mitte mit dem Suchschlüssel und geben den Index zurück, wenn wir eine Übereinstimmung finden. Andernfalls prüfen wir, ob das mittlere Element größer als der Schlüssel oder kleiner als der Schlüssel ist. Wenn die Mitte größer ist, müssen wir nur die erste Hälfte des Arrays überprüfen, da alle Elemente in der zweiten Hälfte des Arrays größer als der Schlüssel sind, also aktualisieren wir das Hoch auf Mitte 1.

Wenn mid kleiner als key ist, müssen wir in ähnlicher Weise in der zweiten Hälfte des Arrays suchen und somit low auf mid+1 aktualisieren. Denken Sie daran, dass die binäre Suche auf dem Algorithmus zum Verringern und Erobern basiert, da wir bei jeder Iteration eine der Hälften des Arrays ignorieren.

Zurück zu unserem Code: Wir haben die main-Methode erstellt. Initialisierte ein sortiertes Array und einen Suchschlüssel, rief die binäre Suche auf und gab die Ergebnisse aus.

Nachdem wir nun die Algorithmen der linearen Suche und der binären Suche durchgegangen sind, wollen wir beide Algorithmen vergleichen.

Lineare Suche vs. binäre Suche

Arbeiten

• Die lineare Suche iteriert durch alle Elemente und vergleicht sie mit dem zu suchenden Schlüssel.
• Die binäre Suche verringert mit Bedacht die Größe des zu durchsuchenden Arrays und vergleicht jedes Mal den Schlüssel mit dem mittleren Element.

Datenstruktur

• Die lineare Suche ist flexibel mit allen Datenstrukturen wie einem Array, einer Liste, einer verketteten Liste usw.
• Die binäre Suche kann nicht für alle Datenstrukturen durchgeführt werden, da wir eine multidirektionale Traversierung benötigen. Daher können Datenstrukturen wie die einfach verkettete Liste nicht verwendet werden.

Voraussetzungen

• Die lineare Suche kann für alle Datentypen durchgeführt werden, die Daten können zufällig oder sortiert sein, der Algorithmus bleibt derselbe. Es sind also keine Vorarbeiten erforderlich.
• Die binäre Suche funktioniert nur in einem sortierten Array. Das Sortieren eines Arrays ist also eine Voraussetzung für diesen Algorithmus.

Anwendungsfall

• Die lineare Suche wird im Allgemeinen für kleinere und zufällig geordnete Datensätze bevorzugt.
• Die binäre Suche wird für vergleichsweise größere und sortierte Datensätze bevorzugt.

Wirksamkeit

• Bei größeren Datensätzen ist die lineare Suche weniger effizient.
• Bei größeren Datensätzen ist die binäre Suche effizienter.

Zeitkomplexität

• Bei der linearen Suche beträgt die Komplexität im besten Fall O (1), wobei das Element am ersten Index gefunden wird. Die Komplexität im schlimmsten Fall ist O (n), wenn das Element am letzten Index gefunden wird oder das Element nicht im Array vorhanden ist.
• Bei der binären Suche beträgt die Komplexität im besten Fall O (1), wobei das Element am mittleren Index gefunden wird. Die Worst-Case-Komplexität ist O( log 2 n).

Probelauf

Nehmen wir an, wir haben ein Array der Größe 10.000.

• Bei einer linearen Suche beträgt die Komplexität im besten Fall O(1) und im ungünstigsten Fall O(10000).
• Bei einer binären Suche beträgt die Komplexität im besten Fall O(1) und im ungünstigsten Fall O( log 2 10000)=O(13,287).

Fazit

Wir haben die Bedeutung des Datenzugriffs in Arrays verstanden, die Algorithmen der linearen Suche und der binären Suche verstanden. Die Codes der linearen Suche und der binären Suche durchgegangen. Verglichen die Unterschiede zwischen linearer Suche und binärer Suche, machte einen Probelauf für ein großformatiges Beispiel.

Jetzt, da Sie sich der Unterschiede zwischen linearer Suche und binärer Suche bewusst sind, versuchen Sie, beide Codes für einen großen Sied-Datensatz auszuführen und die Ausführungszeit zu vergleichen, beginnen Sie, verschiedene Suchalgorithmen zu untersuchen, und versuchen Sie, sie zu implementieren!

Wenn Sie neugierig sind, etwas über Data Science zu lernen, schauen Sie sich das PG Diploma in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1- on-1 mit Mentoren aus der Branche, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.

Lernen Sie Data Science-Kurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.