Was sind lineare und binäre Suche?

Beides sind Suchalgorithmen. Ein Suchalgorithmus ist ein Algorithmus, der in einer Menge von Elementen (z. B. in Form eines Arrays oder einer Liste) versucht, ein bestimmtes Element zu finden.

Lineare Suche ist der einfachste Suchalgorithmus. Dabei wird der Reihe nach jedes Element durchlaufen, bis das gesuchte Element gefunden wurde oder alle Elemente durchlaufen worden sind.

Beispiel: Suche nach Element »5«

1   7   9   0   5   4   8
↑

1   7   9   0   5   4   8
    ↑

1   7   9   0   5   4   8
        ↑

1   7   9   0   5   4   8
            ↑

1   7   9   0   5   4   8
                ↑

Element gefunden!

Im schlimmsten Fall werden bei n Elementen n Vergleiche benötigt.

Implementierung in Pseudocode:

linearSearch(a, e)
Eingabe: Array a mit n Elementen, gesuchtes Element e
Ausgabe: Position von e im Array a oder -1, falls e nicht in a vorkommt



i := 0

while i < n
   if a[i] = e
      return i
   i := i + 1

return -1

Die binäre Suche ist ein effizienterer Suchalgorithmus. Allerdings müssen die Elemente des Arrays sortiert vorliegen. Eine Liste kann nicht verwendet werden, denn es wird eine Datenstruktur benötigt, die einen direkten Zugriff per Index ermöglicht.

Dabei wird zunächst das mittlere Element des Arrays betrachtet. Ist das mittlere Element bereits das gesuchte, ist die Suche erfolgreich. Ansonsten weiß man, dass das gesuchte Element sich in der linken Hälfte befinden muss, falls das gesuchte Element kleiner als das mittlere Element ist, bzw. in der rechten Hälfte, falls es größer ist – die Elemente sind schließlich sortiert.

Somit wird der Algorithmus dann rekursiv (iterativ ist es aber auch möglich) auf diejenige Hälfte angewandt, in der weiterhin gesucht werden muss. Das heißt, man halbiert den Suchbereich solange, bis das gesuchte Element gefunden ist oder der Suchbereich nur noch ein einziges Element umfasst.

Beispiel: Suche nach Element »62« (Suchbereich von [ bis ])

[1  15  23  27  31  39  42  55  58  62  84  85  90  91  98]
                            ↑

Zu klein, suche rechts weiter!

1  15  23  27  31  39  42  55  [58  62  84  85  90  91  98]
                                            ↑

Zu groß, suche links weiter!

1  15  23  27  31  39  42  55  [58  62  84]  85  90  91  98
                                    ↑

Element gefunden!

Im schlimmsten Fall werden bei n Elementen aufgerundet log2(n + 1) Vergleiche benötigt.

Implementierung in Pseudocode:

binarySearch(a, e, start, end)
Eingabe: aufsteigend sortiertes Array a mit n Elementen, gesuchtes Element e, linke Grenze des Suchbereichs start, rechte Grenze des Suchbereichs end
Ausgabe: Position von e im Array a oder -1, falls e nicht in a vorkommt



if end < start
   return -1

mid := start + (end - start) / 2

if e = mid
   return mid
else if e < a[mid]
   return binarySearch(a, e, start, mid - 1)
else
   return binarySearch(a, e, mid + 1, end)

Lineare Suche benötigt am meisten Zeit, ist aber die einzige, die anwendbar ist, wenn die zu durchsuchende Menge nicht irgendwie geordnet vorliegt.

Binäre Suche ist die, welche am wenigsten Zeit benötigt. Leider ist sie nur anwendbar, wenn die zu durchsuchende Menge linear geordnet ist.

Lineare Suche: Du fängst links an und arbeitest dich nach rechts durch, bis du ein passendes Element gefunden hast.

Binäre Suche: Du fängst in der Mitte an, vergleichst das gefundene mit dem, was du suchst. Wenn kleiner gehst du weiter in die Mitte der linken Hälfte, wenn größer gehst du in die Mitte der rechten Hälfte und dann wiederholst du den Schritt solange, bis du was gefunden hast.

Wie du dir sicher mit ein wenig Nachdenken selber zusammenreimen kannst, funktioniert letzteres nur mit einer sortierten Liste, ersteres aber mit jeder beliebigen.