Binäre Suche für Integerarray in rekursiver Funktion

[Dendemeier]

Hallo Zusammen

Folgendes Programm sucht nach einem bestimmten Element in einem Array mittels der Binäre Suche.
Meines erachtens müsste aber ''return binarySearch(array, value, half+1, large)'' ersetzt werden mit
''return binarySearch(array, value, half, large)'' --> also ohen das +1.

Woher kommt das +1??

public class Aufg_4_6 {
	
	public static int binarySearch(int[] array, int value, int small, int large) {
		int half = small + (large-small) / 2; // this one will not overflow
		if (value == array[half]) {
			return half;
		} else {
			if (small == large) {
				return -1;
			} else {
				if (  value < array[half]) {
					return binarySearch(array, value, small, half );
				} else  {
					return binarySearch(array, value, half+1, large);
				}
			}
		}
	}

	public static int binarySearch(int[] array, int value) {
		return binarySearch(array, value, 0, array.length - 1);
	}

	public static void main(String[] args) {
		int[] test = { 3, 5, 8, 10, 21, 23, 35, 42, 67 };
		for (int i = 0; i < test.length; i++) {
			int ii = test[i];
			System.out.println(binarySearch(test, ii-1));
			System.out.println(binarySearch(test, ii));
			System.out.println(binarySearch(test, ii+1));
		}
		System.out.println(binarySearch(test, 17));
	}
}

 

[jstei001]

[c]if (value == array[half]) {
return half;[/c] hier prüfst du ob du den value gefunden hast. Wenn nicht ist er ja logischerweiße Größer oder kleiner als half. Wenn er jetzt Größer ist Dann hast du ja ein neuen Interval zum Prüfen, du weißt aber das er eindeutig größer ist als half. Somit ist er im "kleinsten" Fall (ich weiß doof formuliert) half+1 deshalb wird das als neues small gesetzt. Hoffe es war einigermaßen verständlich.

 

[Dendemeier]

danke, das ist einleuchtend, aber warum ist es dann nicht half-1 um den bereich zwischen small und kleiner als half zu untersuchen?

 

[jstei001]

Bin mir auch nicht 100% sicher aber half wird ja bei der Rekursion dann als large übergeben und ich glaube in der Zeile [c]int half = small + (large-small)[/c] rutsch man dann außerhalb des bereichs weil large-small zu klein war.

 

[SlaterB]

das müsste hier auch möglich sein, das Programm ist noch nicht perfekt,
> if (small == large) {
würde ich auch unbedingt nach vorne, vor die half-Berechnung, ziehen,
dann aber nicht -1 sondern noch schauen ob dieser gemeinsame Index der richtige ist

ob man bei half nachschaut ist auch fast egal, genauso gut könnte man auch jeweils etwa am Anfang und am Ende nachschauen
und die Indexe noch weiter verkleinern,
wenn man nicht mehr bei half nachschaut, sondern alles bis auf Intervalle der Breite 1 runterbricht und nur if (small == large) prüft (was bisher ja nicht der Fall ist) dann wäre es wiederum wichtig, dass half mit drin bleibt in der Rekusion,

vieles zu bedenken, viel effizienter ohne Sortierung wäre eh einfach Durchlauf von Anfang bis Ende

edit: aber ich sehe gerade dass es ja mit Sortierung ist und nicht alles durchsucht wird 😉
einiges gerade falsch gesagt

edit: zur normalen Binärsuche gibt es dann ja auch Internetbeispiele zum Vergleich, etwa
Java Notes: Algorithms: Recursive Binary Search
dort ist es wie hier, unter
Binary search algorithm - Wikipedia, the free encyclopedia
mit -1..


@jstei001
ich denke da besteht kein Problem, die Wahl von half ist auch ziemlich egal, half könnte auch der erste oder letzte Index sein,
solange man beim Rest dann aufpasst

 

[Debdemeier]

also bei einem array der länge 9 z.B. wäre small=0 und half=4, da Array Positionen = bis 8 besitzt.
warum wäre dann 0+(half-1)-0)/2=3/2 ausserhalb des Bereichs?