function SEARCH(Feld a, Element x)
anfang = 0;
ende = |a| − 1;
while ende − anfang > 2 do
ersterIndex = b(2 · anfang + ende) /3c;
zweiterIndex = b(anfang + 2 · ende) /3c;
if x = a[ersterIndex] oder x = a[zweiterIndex] then
return true;
else if
x < a[ersterIndex] then ende = ersterIndex − 1;
else if
x > a[zweiterIndex] then anfang = zweiterIndex + 1;
else
anfang = ersterIndex + 1; ende = zweiterIndex − 1;
for i := anfang to ende do
if x = a then
return true;
return false;
Wir sollen die Laufzeit dieses Programms berechnen und meinen ersten Ansätze sind, dass die Arrays immer gedrittelt werden und n wir immer kleiner.
Müsste dann nicht sowas rauß kommen wie O(log n)?
Ich stehe gerade wirklich auf dem Schlauch..., würde mich über Hilfe freuen!
anfang = 0;
ende = |a| − 1;
while ende − anfang > 2 do
ersterIndex = b(2 · anfang + ende) /3c;
zweiterIndex = b(anfang + 2 · ende) /3c;
if x = a[ersterIndex] oder x = a[zweiterIndex] then
return true;
else if
x < a[ersterIndex] then ende = ersterIndex − 1;
else if
x > a[zweiterIndex] then anfang = zweiterIndex + 1;
else
anfang = ersterIndex + 1; ende = zweiterIndex − 1;
for i := anfang to ende do
if x = a then
return true;
return false;
Wir sollen die Laufzeit dieses Programms berechnen und meinen ersten Ansätze sind, dass die Arrays immer gedrittelt werden und n wir immer kleiner.
Müsste dann nicht sowas rauß kommen wie O(log n)?
Ich stehe gerade wirklich auf dem Schlauch..., würde mich über Hilfe freuen!
