Binäre Suche eines Array

[Jay_Yudhar]

Hallo Leute,
Ich habe ein Java-Code aus dem Internet gefunden und möchte gerne wissen, wie diese die Methode arbeitet. Es handelt sich um ein binäres Suchen eines Array.

Könnt ihr mir vielleicht erklären.

public static int findIndex(int number, int[] values, int begin, int end){
		int step = (end-begin)/2;
		if (values[begin] == number){
			return begin;
		}
		if (step == 0){
			return -1;
		}
		if (values[begin+step] <= number){
			return findIndex(number, values, begin+step, end);
		}
		return findIndex(number, values, begin, begin+step);
	}

 

[Saheeda]

Der Suchraum wird solange weiter halbiert, bis die gesuchte Zahl gefunden wurde. Andernfalls wird -1 ausgegeben.
Die Methode braucht aber ein bereits sortiertes Array, wenn ich das richtig sehe.

 

[Jay_Yudhar]

Hey Saheeda,
danke für deine Antwort.

Mir ist leider noch nicht klar. Also nehmen wir mal an:
value: {2,3,4,5,6,7}
begin: 0
ende: 5
Number: 7 (Was gesucht wird)

dann wird halbiert => 2
step hat den Index 2

Von Zeile 3 bis 8 springen wir, da leider keine von beiden Bedingungen zutrifft.

Zeile 9:
if(value[0+2]<=7) => ist wahr
return findIndex(7, values, 2, 5);

Dann wird solange wiederholt bis das Gesuchte gefunden ist?

 

[Saheeda]

Ja.
Du hast hier eine Rekursion vorliegen, d.h. die Methode ruft sich immer wieder selbst auf, bis die Abbruchbedingung erreicht ist.

Hier wirds auch erklärt:
Javabeginners - Binäre Suche

Animiert:
Binäre Suche on Vimeo

 

[Jay_Yudhar]

Hey Saheeda,
alles klar, habe eben eine eigene Methode geschrieben. Leider ist bei mir, wenn das Index gefunden wurde, wird auf dem Bildschirm gleichzeitig das gesuchte Index und -1(also wenn das Index nicht gefunden wurde) ausgegeben. Hier ist ein kleiner Ausschnitt von meinem Code

int index_mitte = (index_links + index_rechts)/2;
if (arr1.length == 0) { 
            System.out.println(" Array leer.");  
        }
				
			if(arr1[index_mitte] < elem){
			binSuche(arr1, elem, index_mitte+1, index_rechts);
			//index_links = index_mitte +1;
		}
			if(arr1[index_mitte] > elem){
			//index_rechts = index_mitte-1;
			binSuche(arr1, elem, index_links, index_mitte-1);
		}
			else if(arr1[index_mitte] == elem){
				System.out.println(index_mitte);
			}
		return -1;

index_links : start index
index_rechts: end_index
elem: was gesucht wird

wie kann man den fehler beheben?

 

[Saheeda]

Das return -1 steht außerhalb der ifs, wird also in jedem Fall ausgeführt.