Binäre Suche
- Funktioniert nur mit einem vorsortierten Array
- Laufzeitkomplexität: O(log n)
Pseudocode
Funktion BinarySearch(Array, ziel)
links := 0
rechts := Länge(array) - 1
WHILE links <= rechts DO
mitte := (links + rechts) / 2
IF array[mitte] = ziel THEN
Ergebnis := mitte
ELSE IF array[mitte] < ziel THEN
links := mitte + 1
ELSE
rechts := mitte - 1
- Python
- C#
def binary_search(array, ziel):
links = 0
rechts = len(array) - 1
while links <= rechts:
mitte = (links + rechts) // 2
if array[mitte] == ziel:
return mitte
elif array[mitte] < ziel:
links = mitte + 1
else:
rechts = mitte - 1
return -1 # ziel kein element von array
static int BinarySearch(int[] array, int ziel)
{
int links = 0;
int rechts = array.Length - 1;
while (links <= rechts)
{
int mitte = (links + rechts) / 2;
if (ziel == array[mitte])
return mitte;
if (ziel < array[mitte])
links = mitte + 1;
else
rechts = mitte - 1;
}
return -1; // ziel kein element von array
}