Hallo,

und ich habe ein weiteres Problem. Ich soll eine binäre Suche in mein Programm einbauen. Ich habe also eine sortierte Menge. Die Mitte wird ermittelt. Entweder befindet sich die gesuchte Zahl in der unteren oder der oberen Hälfte. Die Hälfte, in der es sich befinden soll, wird noch einmal geteilt, usw.

Mein Quelltext sieht folgendermaßen aus:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public int binSuche(int a){                 int mitte = 0;         int unten = 0;         int oben = feld.length;                 insertionSort();         while (unten < oben) {             mitte = (unten + oben) / 2;             if (feld[mitte] == a) {                 return feld[mitte];               }             else {                 if (a < feld[mitte]) {                     oben = mitte;                 }                 else if (a > feld[mitte]) {                     unten = mitte;                 }                 }         }         return -1;     }

Das Programm funktioniert ganz gut. Leider endet es in einer Endlosschleife, wenn die gesuchte Zahl sich nicht in dem Array feld befindet.
Sieht von euch jemand den Fehler?

Gruß

Cuchulainn

Wenn die vars "oben" und "unten" beide 1 sind, kommt bei "mitte" immer als Ergebnis 1 heraus. Das läuft dann als Endlos-Schleife.

Als Bsp. zum Nachvollziehen nehme an, oben sei 2, unten 0, also mitte = 1.
wenn a > feld[mitte]
unten = mitte = 1; oben = 2
-> mitte = (1 + 2) / 2 = 1

jetzt ist egal was passiert, unten oder oben wird 1 sein und somit mitte immer 1 bleiben.

Hmm, aber dann ist doch die bedingung

(while unten<oben) nicht gegeben und die schleife wird beendet werden, wenn () er im unteren teil weitersuchen würde.

nehmen wir an oben=unten=mitte.

Dann würde die schleife mit 1<1 nicht erfüllt sein und es würde -1 zurückgegeben werden, daran liegt es glaube ich net.

Es liegt wirklich nur daran, wenn er immer im oberen teil weitersucht.

Du musst den oberen teil mit oben=mitte +1 setzen, bzw. den unteren teil mit unten=mitte -1, da du das mittlere objekt ja nicht mehr in die suche einbeziehen willst, da du ja eh weisst, das es dieses objekt nicht ist. dann klappt es auch.

Weil du dann nicht in die beschriebene zwickmühle gerätst, das sich nichts ändert.

Hallo!

Musst du die binäre Suche selbst implementieren oder darfs auch was standardmäßiges sein? -> java.util.Arrays.binarySearch(someType[] t, someType key);

Gruß Tom

Oder so, hey Tom, machs doch net immer so einfach

Hallo!

der "OP" hat ja schließlich lang genug gezappelt ( 30.12.04, 23:34)

Gruß Tom

Hallo und danke für eure Antworten,

Zitat von torsch2711

Du musst den oberen teil mit oben=mitte +1 setzen, bzw. den unteren teil mit unten=mitte -1,

Das hat leider nichts geändert. Er hängt immer noch in der Schleife fest, wenn das Element nicht vorhanden ist.

Zitat von Thomas Darimont

Musst du die binäre Suche selbst implementieren oder darfs auch was standardmäßiges sein?

Ich muss sie leider selbst implementieren

Gruß
Cuchulainn

Hallo!

Schau mal hier:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/*  * Created on 04.01.2005@21:48:31  *  * TODO Licence info  */ package de.tutorials;     /**  * @author Administrator  *  * TODO Explain what I do...  */ public class BinarySort {       public static void main(String[] args) {         int[] array = { 12, 123, 534, 7651, 84131, 99999 };         int pos = binarySearch(array, 99);         System.out.println(pos);     }       public static int binarySearch(int[] feld, int a) {           int mitte = 0;         int unten = 0;         int oben = feld.length;           // insertionSort();         while (unten < oben) {             mitte = (unten + oben) / 2;             if (feld[mitte] == a) {                 return feld[mitte];             } else {                 if (a < feld[mitte]) {                     oben = mitte - 1; // das Element an Stelle 'mitte' wurde                                         // bereits geprüft -> -1                 } else if (a > feld[mitte]) {                     unten = mitte + 1; // das Element an Stelle 'mitte' wurde                                         // bereits geprüft -> +1                 }             }         }         return -1;     } }

Gruß Tom

Ich hab hier noch eine kleinen Fehler entdeckt:

Wenn man nach dem ersten Arrayelement sucht liefert diese Suche -1 (also Fehler).
Dies umgeht man so:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public static int BS(int a[], int value)     {         int mitte = 0;         int unten = 0;         int oben = a.length;           while (unten <[COLOR="Red"]=[/COLOR] oben)         {             mitte = (unten + oben) / 2;             if (a[mitte] == value)             {                 return mitte;             } else             {                 if (value < a[mitte])                 {                     oben = mitte - 1;                     } else if (value > a[mitte])                 {                     unten = mitte + 1;                   }             }         }         return -1;     }

Das <= ermöglicht zugriff auf Element 0 im Array.


Ich weiß dieser Thread ist schon paar Jahre alt, aber ich fand dies wichtig - hoffe dies ist in Ordnung.

Gruß
_Dome_