Lineare und binäre Suchalgorithmen erklärt

Die Fähigkeit, nach bestimmten Daten zu suchen, ist ein wichtiger Aspekt der Informatik. Suchalgorithmen werden verwendet, um nach einem bestimmten Element in einem Datensatz zu suchen.

Algorithmen geben ein boolesches Ergebnis (wahr oder falsch) an eine Suchanfrage zurück. Sie können auch geändert werden, um die relative Position des gefundenen Werts anzugeben.

In diesem Artikel konzentrieren sich die Algorithmen darauf, zu bestimmen, ob ein Wert vorhanden ist.

Lineare Suchalgorithmen

Die lineare Suche wird auch als sequentielle Suche bezeichnet. Bei dieser Art der Suche wird jeder Wert in einer Liste nacheinander auf geordnete Weise besucht, während geprüft wird, ob der gewünschte Wert vorhanden ist.

Der Algorithmus prüft Wert für Wert, bis er den gesuchten Wert findet oder keine Werte mehr zum Suchen haben. Wenn die zu durchsuchenden Werte ausgehen, bedeutet dies, dass Ihre Suchanfrage nicht in der Liste vorhanden ist.

Ein sequentieller Suchalgorithmus nimmt eine Liste von Werten und das gewünschte Element in der Liste als Parameter auf. Das Rückgabeergebnis wird initialisiert als

Falsch und wird sich ändern zu Wahr wenn der gewünschte Wert gefunden ist.

Sehen Sie sich die folgende Python-Implementierung als Beispiel an:

def linearSearch (mylist, item):

gefunden = falsch

Index = 0

while index < len (mylist) und nicht gefunden:

if mylist[index] == Artikel:

gefunden = wahr

anders:

Index = Index+1

Rückgabe gefunden

Algorithmusanalyse

Das beste Szenario tritt ein, wenn das gewünschte Element das erste auf der Liste ist. Der schlimmste Fall tritt ein, wenn das gewünschte Element das letzte auf der Liste ist (das n-te Element). Daher beträgt die Zeitkomplexität für die lineare Suche O(n).

Das durchschnittliche Fallszenario im obigen Algorithmus ist n/2.

Verwandt: Was ist Big-O-Notation?

Modifizierte lineare Suche

Es ist wichtig zu wissen, dass der verwendete Algorithmus davon ausgeht, dass ihm eine zufällige Liste von Elementen bereitgestellt wird. Das heißt, die Listenelemente sind in keiner bestimmten Reihenfolge.

Angenommen, die Elemente befinden sich in einer bestimmten Reihenfolge, sagen wir vom kleinsten zum größten. Es wäre möglich, einige Vorteile bei der Berechnung zu erzielen.

Nehmen Sie ein Beispiel für die Suche nach 19 in der angegebenen Liste: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Nach Erreichen von 23 wird klar, dass das gesuchte Element nicht in der Liste vorhanden ist. Daher wäre es nicht mehr wichtig, die restlichen Listenelemente weiter zu durchsuchen.

Binäre Suchalgorithmen

Sie haben gesehen, wie eine geordnete Liste den Rechenaufwand reduzieren kann. Der binäre Suchalgorithmus nutzt diese Effizienz noch stärker aus, als eine geordnete Liste einführt.

Der Algorithmus beginnt damit, dass er einen mittleren Wert einer geordneten Liste nimmt und prüft, ob es der gewünschte Wert ist. Ist dies nicht der Fall, wird geprüft, ob der Wert kleiner oder größer als der gewünschte Wert ist.

Wenn es weniger ist, müssen Sie die untere Hälfte der Liste nicht überprüfen. Andernfalls, wenn es größer ist, wird es in die obere Hälfte der Liste verschoben.

Verwandt: Was ist Rekursion und wie wird sie verwendet?

Unabhängig davon, welche Unterliste (links oder rechts) gewählt wird, wird erneut der Mittelwert bestimmt. Der Wert wird erneut überprüft, ob es sich um den erforderlichen Wert handelt. Ist dies nicht der Fall, wird geprüft, ob er kleiner oder größer als der angeforderte Wert ist.

Dieser Vorgang wird wiederholt, bis ein Wert gefunden wird, falls er vorhanden ist.

Die folgende Python-Implementierung ist für den binären Suchalgorithmus.

def binarySearch (mylist, item):

niedrig = 0

hoch = len (mylist) - 1

gefunden = falsch

während niedrig <= hoch und nicht gefunden:

mittel = (tief + hoch) // 2

if mylist[mid] == Artikel:

gefunden = wahr

elif item < mylist[mid]:

hoch = mittel - 1

anders:

niedrig = mittel + 1

Rückgabe gefunden

Algorithmusanalyse

Das beste Szenario tritt ein, wenn das gewünschte Element das mittlere Element ist. Das Worst-Case-Szenario ist jedoch nicht so einfach. Folgen Sie der folgenden Analyse:

Nach dem ersten Vergleich bleiben n/2 Elemente übrig. Nach dem zweiten bleiben n/4 Elemente übrig. Nach dem dritten, n/8.

Beachten Sie, dass sich die Anzahl der Elemente halbiert, bis sie n/2i erreichen, wobei i die Anzahl der Vergleiche ist. Nach all der Aufteilung haben wir am Ende nur 1 Artikel.

Dies impliziert:

n/2i=1

Daher ist die binäre Suche O(log n).

Weiter zur Sortierung

Bei der binären Suche haben wir einen Fall betrachtet, in dem das angegebene Array bereits geordnet war. Angenommen, Sie haben einen ungeordneten Datensatz und möchten eine binäre Suche durchführen. Was würdest du tun?

Die Antwort ist einfach: sortieren. Es gibt eine Reihe von Sortiertechniken in der Informatik, die gut erforscht sind. Eine dieser Techniken, die Sie mit dem Studium beginnen können, ist der Auswahlsortieralgorithmus, während wir auch viele Anleitungen zu anderen Bereichen haben.

So verwenden Sie die Auswahlsortierung

Die Sortierung der Auswahl ist für Anfänger etwas schwierig zu verstehen, aber es ist nicht allzu schwierig, wenn Sie erst einmal den Schwung der Dinge haben.

Weiter lesen

Über den Autor