Algorithmus für kleinstes und größtes Element

[serious]

Hallo liebe community,
ich habe folgendes Problem.

Gebt einen Algorithmus als Pseudocode an, der gleichzeitig das Minimum und das
Maximum bestimmt. Dieser Algorithmus soll echt weniger als 2n-3 Vergleiche von
Elementen durchführen.
Wir wollen im Folgenden der Einfachheit halber annehmen, dass ein Array der Länge n
gegeben ist, wobei n = 2k gerade ist. Weiterhin sollen alle Arrayelemente unterschiedlich
sein, so dass ein Vergleich immer ein eindeutiges Ergebnis hat.

Den normalen Vergleich(die ersten beiden Elemente miteinander vergleichen, Min / Max festlegen und dann mit den restlichen Arrayeinträgen vergleichen), den ich bisher immer verwendet habe (programmiere seit ca. 1 1/2 Monaten),
kann ich hier nicht benutzen da er 2n-2 Vergleiche braucht.
Als zweites hatte ich mir überlegt, ob ich das Array nach Größe sortiere. Aber ich glaube, dass ich hier noch weit mehr Vergleiche bräuchte, als normal.

Hat jemand einen Tipp? Mir ist bisher auch noch nicht bewusst, was mir die Tatsache nutzt, dass die Arraylänge gerade ist.

Mit freundlichen Grüßen,
Serious

 

[XHelp]

Der Hinweis mit 2k Elemente hat wohl zu bedeuten, dass es 2 gleich große Teillisten gibt. Also müsstest du schon irgendwas mit den Hälften anstellen. z.B.:

for (int i=0;i<array.length/2;i++) {
  if (array[i]>array[array.length-1-i]) {
    swap(i,array.length-1-i);
  }
}

Dadurch bringst du schon die kleinste Zahl in die linke Hälfte und die größte Zahl in die rechte Hälfte. Das machst du mit

n/2

vergleichen
Jetzt überlege wie du an die kleinste und die größte Zahl kommst.

Und im Endeffekt bist du bei

(3n-4)/2

und es ist kleiner als

(4n-6)/2

, was in der Aufgabenstellung vorgegeben ist.

Da gibt es aber bestimmt auch andere Lösungsansätze.

P.S. n=2 kannst du als Sonderfall abstempeln. Denn ein Algo mit echt kleiner als 1 Vergleichen wirst du wohl nicht finden.

 

[serious]

Danke für die Hilfe. Hab das erstmal in Javacode umgesetzt. Jetzt muss ich mich nur nochmal mit Pseudocode auseinandersetzen.

Danke nochmal. Grüße,
Serious