In der Informatik, geradlinigen Suche oder folgenden Suche ist eine Methode, für einen besonderen Wert in einer Liste zu finden, die daraus besteht, jedes seiner Elemente einer nach dem anderen und in der Folge zu überprüfen, bis der gewünschte gefunden wird.

Geradlinige Suche ist der einfachste Suchalgorithmus; es ist ein spezieller Fall der Suche der rohen Gewalt. Seine Grenzfall-Kosten sind zur Zahl der Elemente in der Liste proportional; und ist auch seine erwarteten Kosten, wenn nach allen Listenelementen ebenso wahrscheinlich gesucht wird. Deshalb, wenn die Liste mehr hat als einige Elemente, werden andere Methoden (wie binäre Suche oder hashing) schneller sein, aber sie erlegen auch zusätzliche Voraussetzungen auf.

Analyse

Für eine Liste mit n Sachen ist der beste Fall, wenn der Wert dem ersten Element der Liste gleich ist, in welchem Fall nur ein Vergleich erforderlich ist. Der Grenzfall ist, wenn der Wert nicht in der Liste ist (oder nur einmal am Ende der Liste vorkommt), in welchem Fall n Vergleiche erforderlich sind.

Wenn der Wert, der wird sucht, k Zeiten mit der Liste vorkommt, und die ganze Einrichtung der Liste ebenso wahrscheinlich ist, ist die erwartete Zahl von Vergleichen

:

\begin {Fälle}

n & \mbox {wenn} k = 0 \\[5pt]

\displaystyle\frac {n + 1} {k + 1} & \mbox {wenn} 1 \le k \le n.

\end {Fälle }\

</Mathematik>

Zum Beispiel, wenn der Wert, der wird sucht, einmal in der Liste vorkommt, und die ganze Einrichtung der Liste ebenso wahrscheinlich ist, ist die erwartete Zahl von Vergleichen. Jedoch, wenn es bekannt ist, dass es einmal dann am grössten Teil von n vorkommt - sind 1 Vergleiche erforderlich, und die erwartete Zahl von Vergleichen ist

:

(zum Beispiel für n = 2 ist das 1, entsprechend einer einzelnen Konstruktion "wenn dann sonst").

Jeder Weg, asymptotisch die Grenzfall-Kosten und die erwarteten Kosten der geradlinigen Suche ist beide O (n).

Ungleichförmige Wahrscheinlichkeiten

Die Leistung der geradlinigen Suche verbessert sich, wenn der Sollwert mit größerer Wahrscheinlichkeit in der Nähe vom Anfang der Liste sein wird als zu seinem Ende. Deshalb, wenn einige Werte viel mit größerer Wahrscheinlichkeit gesucht werden als andere, ist es wünschenswert, sie am Anfang der Liste zu legen.

Insbesondere wenn die Rasterpunkte in der Größenordnung von der abnehmenden Wahrscheinlichkeit eingeordnet werden, und diese Wahrscheinlichkeiten geometrisch verteilt werden, sind die Kosten der geradlinigen Suche nur O (1). Wenn die Tabellengröße n große genug, geradlinige Suche ist, wird schneller sein als binäre Suche, deren Kosten O sind (loggen Sie n).

Anwendung

Geradlinige Suche ist gewöhnlich sehr einfach durchzuführen und ist praktisch, wenn die Liste nur einige Elemente hat, oder wenn sie eine einzelne Suche in einer nicht eingeordneten Liste durchführt.

Wenn viele Werte in derselben Liste gesucht werden müssen, zahlt sie häufig, um die Letzteren zu vorbearbeiten, um eine schnellere Methode zu verwenden. Zum Beispiel kann man die Liste sortieren und binäre Suche verwenden, oder jede effiziente Suchdatenstruktur davon bauen. Wenn der Inhalt der Listenänderung oft, wiederholte Reorganisation mehr Schwierigkeiten sein kann, als es wert ist.

Infolgedessen, wenn auch in der Theorie andere Suchalgorithmen schneller sein können, als geradlinige Suche (zum Beispiel binäre Suche), in der Praxis sogar auf dem Medium Reihe nach Größen geordnet hat (ungefähr 100 Sachen oder weniger) es unausführbar sein könnte, irgend etwas anderes zu verwenden. Auf der größeren Reihe hat es nur Sinn, anderen zu verwenden, schneller Methoden zu suchen, wenn die Daten groß genug sind, weil die anfängliche Zeit (um Sorte) die Daten vorzubereiten, mit vielen geradlinigen Suchen vergleichbar

ist

Pseudocode

Schicken Sie Wiederholung nach

Der folgende Pseudocode beschreibt eine typische Variante der geradlinigen Suche, wo das Ergebnis der Suche irgendein die Position des Rasterpunktes sein soll, wo der Sollwert gefunden wurde; oder eine ungültige Position Λ, um anzuzeigen, dass das gewünschte Element in der Liste nicht vorkommt.

Für jeden Artikel in der Liste:

wenn dieser Artikel den Sollwert, hat

hören Sie die Suche auf und geben Sie die Position des Artikels zurück.

Geben Sie Λ zurück.

In diesem Pseudocode wird die letzte Linie nur durchgeführt, nachdem alle Rasterpunkte mit niemandem das Zusammenbringen untersucht worden sind.

Wenn die Liste als eine Reihe-Datenstruktur versorgt wird, kann die Position der Index des Artikels gefunden (gewöhnlich zwischen 1 und n, oder 0 und n&minus;1) sein. In diesem Fall kann die ungültige Position Λ jeder Index vor dem ersten Element (solcher als 0 oder &minus;1, beziehungsweise) oder nach dem letzten (n+1 oder n, beziehungsweise) sein.

Wenn die Liste eine einfach verbundene Liste ist, dann ist die Position des Artikels seine Verweisung, und Λ ist gewöhnlich der ungültige Zeigestock.

Rekursive Version

Geradlinige Suche kann auch als ein rekursiver Algorithmus beschrieben werden:

LinearSearch (Wert, Liste)

wenn die Liste leer ist, geben Sie Λ zurück;

sonst

wenn der erste Artikel der Liste den Sollwert hat, geben Sie seine Position zurück;

geben Sie sonst LinearSearch (Wert, Rest der Liste) zurück

Suche in umgekehrter Reihenfolge

Die geradlinige Suche in einer Reihe wird gewöhnlich durch das Steigern einer Index-Variable programmiert, bis sie den letzten Index erreicht. Das verlangt normalerweise zwei Vergleich-Instruktionen für jeden Rasterpunkt: Ein, um zu überprüfen, ob der Index das Ende der Reihe und eines anderen erreicht hat, um zu überprüfen, ob der Artikel den Sollwert hat. In vielen Computern kann man die Arbeit des ersten Vergleichs reduzieren, indem man die Sachen in umgekehrter Reihenfolge scannt.

Nehmen Sie an, dass eine Reihe mit Elementen mit einem Inhaltsverzeichnis versehen 1 zu n nach einem Wert x gesucht werden soll. Der folgende

Pseudocode führt eine Vorwärtssuche durch, n + 1 zurückkehrend, wenn der Wert nicht gefunden wird:

Gehen Sie i zu 1 unter.

Wiederholen Sie diese Schleife:

Wenn i> n, dann über die Schleife herrschen Sie.

Wenn [ich] = x, dann über die Schleife herrschen Sie.

Gehen Sie i zu mir + 1 unter.

Kehren Sie i zurück.

Der folgende Pseudocode sucht die Reihe in der Rückordnung, 0 zurückkehrend, wenn das Element nicht gefunden wird:

Gehen Sie i zu n unter.

Wiederholen Sie diese Schleife:

Wenn ich  0, dann über die Schleife herrschen Sie.

Wenn [ich] = x, dann über die Schleife herrschen Sie.

Gehen Sie i zu mir &minus unter; 1.

Kehren Sie i zurück.

Die meisten Computer haben eine bedingte Zweiginstruktion, die das Zeichen eines Werts in einem Register oder das Zeichen des Ergebnisses der neusten arithmetischen Operation prüft. Man kann diese Instruktion verwenden, die gewöhnlich schneller ist, als ein Vergleich gegen einen willkürlichen Wert (das Verlangen einer Subtraktion), um den Befehl durchzuführen, "Wenn ich  0, dann über die Schleife herrschen".

Diese Optimierung wird leicht durchgeführt, wenn man in der Maschine oder Zusammenbau-Sprache programmiert. Diese Zweiginstruktion ist auf typischen Programmiersprachen auf höchster Ebene nicht direkt zugänglich, obwohl viele Bearbeiter im Stande sein werden, diese Optimierung selbstständig durchzuführen.

Das Verwenden eines Wächters

Eine andere Weise, die Gemeinkosten zu reduzieren, soll die ganze Überprüfung des Schleife-Index beseitigen. Das kann durch das Einfügen des gewünschten Artikels selbst als ein Wächter-Wert am weiten Ende der Liste, als in diesem Pseudocode getan werden:

Gehen Sie [n + 1] zu x. unter

Gehen Sie i zu 1 unter. Wiederholen Sie diese Schleife: Wenn [ich] = x, dann über die Schleife herrschen Sie. Gehen Sie i zu mir + 1 unter. Kehren Sie i zurück.

Mit diesem Strategem ist es nicht notwendig, den Wert von mir gegen die Listenlänge n zu überprüfen: Selbst wenn x nicht in zunächst war, wird die Schleife wenn ich = n + 1 enden. Jedoch ist diese Methode nur möglich, wenn die Reihe [n + 1] einsteckt, besteht, aber wird nicht sonst verwendet. Ähnliche Vorbereitungen konnten getroffen werden, wenn die Reihe in umgekehrter Reihenfolge gesucht werden sollte, und Element (0) verfügbar war.

Obwohl die durch diese Tricks vermiedene Anstrengung winzig ist, ist es noch ein bedeutender Bestandteil der Gemeinkosten, jeden Schritt der Suche durchzuführen, die klein ist. Nur wenn viele Elemente wahrscheinlich verglichen werden, wird es lohnende in Betracht ziehende Methoden sein, die weniger Vergleiche machen, aber andere Voraussetzungen auferlegen.

Geradlinige Suche auf einer geordneten Liste

Für geordnete Listen, auf die folgend, wie verbundene Listen oder Dateien mit Aufzeichnungen der variablen Länge zugegriffen werden muss, die an einem Index Mangel haben, kann die durchschnittliche Leistung durch das Aufgeben am ersten Element verbessert werden, das größer ist als der unvergleichliche Zielwert, anstatt die komplette Liste zu untersuchen.

Wenn die Liste als eine bestellte Reihe versorgt wird, dann ist binäre Suche fast immer effizienter als geradlinige Suche als mit n> 8, sagen wir, wenn es einen Grund nicht gibt anzunehmen, dass die meisten Suchen für die kleinen Elemente in der Nähe vom Anfang der sortierten Liste sein werden.

Siehe auch

• Dreifältige Suche
• Hash-Tabelle
• Geradliniges Suchproblem

Links