Nein. Lineare Suche kann verwendet werden, um die Einträge der Reihe zu durchsuchen, beginnend mit dem ersten Eintrag.
Die lineare Suche ist langsam. Stellt Euch vor wir würden in einem Wörterbuch etwas von Hand suchen. Das Nachschlagen von "Zebra" würde sehr lange dauern, wenn wir von der ersten Seite an alle vorherigen Einträge durchsehen müssten.
Normalerweise suchen wir nach einem Eintrag, indem wir raten wo er ungefähr im Wörterbuch stehen könnte und schlagen das Wörterbuch an dieser Stelle auf. Wenn wir richtiglagen, sind wir fertig. Andernfalls verfeinern wir die Suche, indem wir von der aufgeschlagenen Seite aus die Suche entweder vorwärts oder rückwärts fortsetzen. Das ist möglich, weil die Wörter in geordneter Reihenfolge stehen.
Wenn ein Array sortiert ist, kann ein Algorithmus namens Binäre Suche verwendet werden, um nach einem Eintrag zu suchen. Dieser Algorithmus funktioniert in etwa so, wie die Suche in einem Wörterbuch. Die Klasse Arrays verfügt über mehrere Methoden binarySearch(), mit denen Arrays von primitiven Typen oder Objektreferenzen schnell durchsucht werden können.
Betrachten wir eine Methode, die ein Array von Objektreferenzen durchsucht.
static int binarySearch(Object[] array, Object key)
Durchsucht das Array mit der Methode compareTo() nach einem Objekt das mit key übereinstimmt. Wenn das Objekt gefunden wird, wird der Index des Objekts im Array zurückgegeben. Andernfalls wird ein negativer Wert zurückgegeben.
Die Details (könnten vorerst übersprungen werden): Wenn der Rückgabewert R negativ ist, dann ist (-R) eine Zelle weiter als die Stelle, an der sich key befinden würde, wenn er im Array wäre. Wir können diesen Wert verwenden, um ein neues Element an der richtigen Stelle in das Array einzufügen. (Wir verschieben Elemente bei (-R) und darüber, um Platz zu schaffen.)
Wenn (-R) gleich der Größe des Arrays ist, dann befindet sich der Schlüssel nicht im Array und sollte ganz am Ende eingefügt werden, aber es ist kein Platz.
Für jetzt wollen wir die binäre Suche verwenden und keine neuen Einträge in das Array einfügen.
Bei einem Wörterbuch mit 10 Einträgen, macht es da einen Unterschied wie schnell die Suche ist?