Mithilfe solcher Aufgaben kannst du üben eigenen Code zu schreiben und danach natürlich die Lösung anschauen ob die Aufgabe richtig verstanden wurde . Wichtig hierbei ist natürlich, dass es nicht die richtige Lösung gibt und die Lösung von mir lediglich dazu dient eine bereitzustellen und Anreize zu bieten, sollte man mal nicht weiter kommen.

Aufgabenstellung

Ziel ist es ein vor sortiertes Array nach einem bestimmten Wert zu durchsuchen. Das vorgehen ist sehr einfach. Wir suchen eine bestimmte Zahl in einem sortierten bestimmten Umfeld ,sollte die Zahl kleiner sein als die Mitte unseres Feldes, dann verkleinern wir unseren Bereich in die richtige Richtung um so die Zahl immer weiter einzukreisen.Um es an einem Beispiel zu zeigen. Suchen wir in die Zahl 15 in dem unten stehenden Array.

Jetzt vergleichen wir die Mitte also den 4. Platz unseres Array mit unserer gesuchten Zahl. Da die Zahl kleiner als unsere gesuchte ist, verkleinern wir den Suchbereich.

Jetzt können wir von unserem Array wieder die Mitte nehmen (da es hier gerade ist, nehmen wir die "untere Mitte" also die Zahl mit dem Index 6)Da unsere Zahl wieder größer ist müssen wir den Suchbereich wieder verkleinern.

Jetzt nehmen wir wieder die "Mitte" also die Zahl mit dem Index 7. Da beide Zahlen gleichgroß sind haben wir unser Ergebnis.

Hinweis

Solltest du starke Probleme mit der Aufgabe haben, lies dir bitte nochmal die unten verlinkten Artikel durch. Zum Ende des Artikels

Lösungsweg

Wir fangen an, indem wir uns überlegen was wir alles benötigen. Wir brauchen ein Array, eine Zahl die wir finden wollen und eine obere bzw. untere Grenze. Mit diesen Sachen können wir den Funktionskopf schreiben. Als nächstes überlegen wir uns wie wir an die "untere Mitte" kommen. Hier nehme ich einfach unsere obere Grenze + die untere Grenze und dividiere sie durch 2 und weil es beides Integers sind, habe ich die untere Grenze gefunden.

Bisheriger Code

1func search(find, low, high int, arr []int) int {
2	index := (low + high) / 2
3}

Da wir die Mitte jetzt haben, müssen wir nur noch die Zahlen mit dem Index vergleichen und können anschließend die Funktion einfach erneut aufrufen um so die Rekursion zu benutzen.

 1func search(find, low, high int, arr []int) int {
 2	index := (low + high) / 2
 3
 4	if arr[index] == find {
 5		return index
 6	} else if low > high {
 7		return -1
 8	} else if arr[index] < find {
 9		return search(find, index+1, high, arr)
10	} else {
11		return search(find, low, index-1, arr)
12	}
13
14}

Aufgerufen werden kann die Funktion, indem man zuerst ein Array initialisiert und mit Werten füllt und anschließend die verschiedenen Werte mitgibt.

1func main() {
2	arr := []int{2, 3, 5, 7, 9, 11, 13, 15, 17, 19}
3
4	fmt.Println("Index", search(11, 0, len(arr)-1, arr))
5
6}

Kompletter Quellcode

 1package main
 2
 3func search(find, low, high int, arr []int) int {
 4	index := (low + high) / 2
 5
 6	if arr[index] == find {
 7		return index
 8	} else if low > high {
 9		return -1
10	} else if arr[index] < find {
11		return search(find, index+1, high, arr)
12	} else {
13		return search(find, low, index-1, arr)
14	}
15
16}
17
18func main() {
19	arr := []int{2, 3, 5, 7, 9, 11, 13, 15, 17, 19}
20
21	fmt.Println("Index", search(11, 0, len(arr)-1, arr))
22
23}

Verweise

• Rekursionen

• Golang Rekursion

• Weitere Rekursions Aufgaben

• Alle Golang Aufgaben