Binäre Suche

cuchulainn

Mitglied
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:
    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.
 
Zuletzt bearbeitet:
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
 
Hallo und danke für eure Antworten,

torsch2711 hat gesagt.:
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. :(

Thomas Darimont hat gesagt.:
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:
/*
 * 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:
    public static int BS(int a[], int value)
    {
        int mitte = 0;
        int unten = 0;
        int oben = a.length;

        while (unten <= 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_
 
Zuletzt bearbeitet:
Zurück