Suchverfahren: Binäre Suche


Die binäre Suche ist der einfachste Suchalgorithmus, welcher nicht nur stupide durch alle Element läuft. Der Algorithmus arbeitet auf einem bereits sortierten Feld(Array) und hat im besten Fall bereits mit nur einem Vergleich einen Treffer.

Das Array wird dabei zunächst in zwei gleich große Hälften aufgeteilt. Das Element in der Mitte wird dann mit dem zu suchenden Wert verglichen. Stimmt der Wert überein, so ist die Suche damit beendet. Trifft dies nicht zu, so wird geschaut ob der zu suchende Wert kleiner oder größer ist als das Element in der Mitte. Je nachdem wird der Suchalgorithmus dann auf der kleineren oder größeren Seite fortgesetzt. Die jeweilige Seite wird zu dem neuen Suchbereich mit dem der Algorithmus von neuem gestartet wird. Der Algorithmus lässt sich damit wunderbar in einer Schleife implementieren.

In dem Beispiel wird die Nummer Sieben gesucht. Zuerst wird das mittlere Element, die Neun mit der Sieben verglichen. Das Sieben kleiner ist wird die Suche mit der linken Array-Hälfte fortgesetzt. Gibt es keine Mitte so wird wahlweise auf oder abgerundet. Im nächsten Schritt wird die Vier mit der Sieben verglichen und dann die Fünf. In beiden Fällen ist die Sieben größer, weswegen jeweils die rechte Array-Hälfte ausgewählt wird, bis die Sieben gefunden wurde und die Suche damit beendet ist.
public static <T extends Comparable<T>> int binarySearch(T[] array, T item) {
	int low = 0;
	int high = array.length - 1;
	
	while(low <= high) {
		int mid = (high - low)/2 + low;
		int compare = item.compareTo(array[mid]);

		if (compare == 0) {
			return mid;
		}
		else if (compare < 0) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return -1;
}

Komplexität

BestO(1)
AverageO(log n)
WorstO(log n)