BinarySearch, Variante 3 (unendliche Listen)

Hierbei handelt es sich um eine für große Listen optimierte Variante. Der Vorteil dieses Verfahrens ist, daß die Größe der Liste zu Beginn der Suche nicht bekannt sein muß. Außerdem ist die Suche schnell, wenn das gesuchte Element in der Nähe des Ausgangspunktes ist.

Variante 3.a (iterativ)
Typ optimiert
Eigenschaften iterativ, nicht parallelisierbar
Datenstrukturen Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(1) Θ(logn) Ο(logn)
Vergleiche (found) 2 2logn-2 2logn
Vergleiche (not found) 1 2logn-2 2logn

listele binarysearch(listele first, element ele) {
  sort(first);
  if (ele < first.value) then
    return null;
  }
  i:= 1;
  do {
    last:= next(first, i);
    if (ele <= last.value) then {
      result binary(first, last, ele);
    }
    i:= i*2;
    first:= last.next;
  while (first <> null);
  return null;
}

listele next(listele first, int count) {
  r:= first;
  while ((count > 0) and (r.next <> null)) {
    r:= r.next;
    count--;
  }
  return r;
}

listele binary(listele first, listele last, element ele) {
 ... // normale binäre Suche
}