Frage zu Java Programm (Arrays)
 

Ein Freund von mir wollt mir das binäre suchen in einem Array in Java erklären jedoch bin ich damit etwas überfordert. er hat mir folgendes geschickt und hat gemeint jetzt soll ich mal das Java Programm formulieren. Nur so recht kann ich das noch nicht da ich ja noch Programmieranfänger bin. Kann mir jemand helfen wie das Java Programm aussehen müsste damit das ganze läuft?

Wäre super wenn mir jemand helfen kann.

Dankeschön!

Beispiel:

oben und unten sind Variablen.
Initialisieren würd ich sie so:

unten = 0
oben = length(array)-1 // weil wir ja von 0 weg zählen

Bei GEFUNDEN machst eben das, was du machen willst, wenn die Suche erfolgreich war.

OK:
machen wir mal ein sortiertes Array (wenns unsortiert ist, gehts nicht)

a = [1, 5, 6, 8, 10, 12, 13, 15, 20]
also
a[0] = 1
a[1] = 5
a[2] = 6
usw
Insgesamt hat das Array a 9 Elemente (von 0 bis 8)

unten=0
oben ist 8

Gesucht ist 12.

Gut gemmas an:

Erster Durchlauf:
mitte = 0 + ((8-0)/2) = 4
a[4] = 10
12 > 10
also
unten = mitte
unten = 4
Jetzt wissen wir, dass die gesuchte Zahl nur zwischen a[4] und a[8] liegen kann.

Zweiter Durchlauf
mitte = 4 + ((8-4)/2) = 6
a[6] = 13
12 < 13
also
oben = mitte
oben = 6
Jetzt wissen wir, dass die gesuchte Zahl nur zwischen a[4] und a[6] liegen kann

Dritter Durchlauf
mitte = 4 + ((6-4)/2) = 5
a[5] = 12
12 == 12
BINGO!
Ausgabe ("Der gesuchte Wert wurde im Feld 5 gefunden")

Eventuell checkst am Ende noch, ob du überhaupt was gefunden hast, und gibst ansonsten "Leider nicht gefunden" aus.

falls du es noch nicht verstanden hast:

vorraussetzung:
ein aufsteigend geordnetes array
eine gesuchte zahl

du hast dein array, nimmst genau die mittlere zahl (bzw bei gerader anzahl die linksmittige).
je nachdem ob diese größer oder kleiner schmeißt du die linke bzw die rechte hälfte sozusagen weg und konzentrierst dich nur mehr auf die andere hälfte.

dort nimmst du wieder die mittlere zahl und wiederholst den vorgang.

jedesmal wird das array so um die hälfte kleiner und irgendwann ist die mittlere zahl deine gesuchte zahl.
wenn die mittlere zahl gleich der linken grenze ist, gibts die zahl nicht.

geht bei absteigend geordneten arrays umgekehrt.

beispielcode für c (is wenig unterschied zu java)
http://gtsun.et.fh-osnabrueck.de/leh...pt/node28.html