[informatik-bonn] Re: InfoIII
- From: Lutz Oberst <oberst@xxxxxxxxxxx>
- To: informatik-bonn@xxxxxxxxxxxxx
- Date: Sat, 1 Feb 2003 19:32:47 +0100
On Fri, Jan 31, 2003 at 07:22:31PM +0100, Sebastian Bothe wrote:
> Hallo zusammen!
Moin,
> 3.) Auf Zettel 2 Aufgabe 4 ist die Frage nach einem Algo der mit möglichst
> wenigen vergleichen eine Zahl in dem Array findet. Dabei ist als zusätzliche
> Info gegeben, daß sich die Zahlen jeweils Betragsmäßig bloß max um 1
> unterscheiden. Auch soll die gesuchte Zahl \ge der ersten im Array und \le
> der letzten sein. Meli's Tip war binäre Suche- Das funktioniert auch
> erstaunlicher Weise, aber ich kann mir nicht erklären wieso- Denn für
> Binärsuche sollte doch das Array sortiert sein-
Der Kanckpunkt der Binären-Suche ist ja die Entscheidung
links oder rechts von der Mitte weiterzusuchen.
Da F[] nicht sortiert ist weißt du zwar per se nicht, ob sich
das gesuchte Element links oder rechts der Mitte befindet,
aber da y \leq z \leq x weißt du, daß falls F[mitte] < z \leq x
z rechts der Mitte und falls F[mitte] > z > y links
liegt. (Zwischenwertsatz)
> Das was sich da Jochen
> ausgedacht hat ist wohl richtig, aber ich verstehs nicht :-(
Das was da bei euch steht kapiere ich auch nicht. Hat
das mal jemand zu compilen versucht?
> Gruß
> Sebastian
HTH, Lutz
--
"We left all that stuff out. If there's an error, we have this routine
called panic, and when it is called, the machine crashes, and you
holler down the hall, 'Hey, reboot it.'"
-- Dennis Ritchie about error code handling in UNIX.
Other related posts:
