Binäre Suche

M

MoeX

Mitglied
Hallo zusammen,

ich versuche mich zZ an der binären Suche einer Zahl in einer sortierten Folge.
Ich habe es nun geschafft, dass es funktioniert, aber wirklich glücklich bin ich damit nicht:

Java: 
public class BinaereSuche{

	public static int binaer(int[]z, int k){
		int rechts=z.length;
		int links=0;
		int m= (links+rechts)/2;
		do{if (z[m]==k) return (m+1);
			else if (z[m]<k) links = (m+1);
			else rechts =(m-1);
			m = (links+rechts)/2;
		}
		while (links != rechts);
	if (m==rechts) return (rechts+1);
	else return (z.length+5);
	}


	public static void main (String[]args){
		int [] arr= {3,5,7,8,9,12,17,22,23};
		int k= 3;
		int erg = binaer (arr, k );
		System.out.println(erg);

	}
}

Und zwar kommt mir die do-while Schliefe irgendwie unelegant vor.
Zum einen weil ich sowohl vor als auch in der Schleife das m auf die selbe Art und Weiße bestimmen muss und zum anderen stört es mich, dass ich nach dem Abbruch noch überprüfen muss ob m=links=rechts ist.
Aber mir fällt nichts besseres ein^^

Da gibt es doch bestimmt elegantere Abbruchbedingungen, oder eine möglichkeit das mit einer for-Schleife zu lösen oder so...

Danke für eure Ideen ;-)
 
Landei

Landei

Top Contributor
Ich würde es rekursiv machen, ist hier am bequemsten:

Java: 
public class BinaereSuche {
    public static int binaer(int[] array, int value) {
        return binaer(array, value, 0, array.length);
    }

    private static int binaer(int[] array, int value, int left, int right) {
        if (left + 1 == right) {
            return left;
        }
        int middle = (left + right) / 2;
        boolean smaller = value < array[middle];
        return binaer(array, value, 
                smaller ? left : middle, 
                smaller ? middle : right);
    }

    public static void main(String[] args) {
        int[] array = {3, 5, 7, 8, 9, 12, 17, 22, 23};
        int value = 60;
        int erg = binaer(array, value);
        System.out.println(erg);

    }
}

Allerdings musst du aufpassen, was genau der Rückgabewert bedeutet. In meiner Implementierung ist es der Index der größten Zahl des Arrays, die kleiner oder gleich dem gesuchten Wert ist.
 

Aktuelle Jobs

Neue Themen


Oben