Sortierte Daten durchsuchen
Binärsuche
Sortierte Daten durchsuchen ist eine kostenlose Go Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Go Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Go Academy-Kurs umfasst insgesamt 4 Lektionen.
Warum sortierte Daten durchsuchen
Sobald ein Slice sortiert ist, können Sie Elemente mithilfe einer binären Suche deutlich schneller finden, statt jedes Element einzeln zu prüfen.
Das Go-Paket sort stellt Suchhilfen bereit, die in logarithmischer Zeit ausgeführt werden.
Linear oder binär
Eine lineare Suche prüft jedes Element nacheinander (O(n)). Eine binäre Suche halbiert den Suchbereich in jedem Schritt (O(log n)), setzt aber voraus, dass die Daten zuvor sortiert wurden.
sort.SearchInts
sort.SearchInts findet den Index, an dem sich ein Wert befindet oder an dem er eingefügt werden müsste, damit das Slice sortiert bleibt. Das Slice muss bereits aufsteigend sortiert sein.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Einen Treffer bestätigen
SearchInts gibt auch dann einen Index zurück, wenn der Wert nicht vorhanden ist – die Einfügeposition. Bestätigen Sie den Treffer daher immer mit i < len(s) && s[i] == target.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
target := 4
i := sort.SearchInts(nums, target)
found := i < len(nums) && nums[i] == target
fmt.Println("index:", i, "found:", found)
}Einfügeposition
Wenn ein Wert fehlt, ist der zurückgegebene Index genau die Position, an der Sie ihn einfügen würden, damit die Reihenfolge erhalten bleibt. Hier würde 4 an Index 2 eingefügt.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7}
i := sort.SearchInts(nums, 4)
fmt.Println("insert 4 at index:", i)
}SearchStrings
sort.SearchStrings macht dasselbe für ein sortiertes String-Slice.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}Das allgemeine sort.Search
sort.Search ist die flexible Grundlage. Sie übergeben eine Länge und eine Funktion f, die zunächst false und danach true liefert. Zurückgegeben wird der kleinste Index, an dem f wahr ist.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{2, 4, 6, 8, 10}
i := sort.Search(len(nums), func(i int) bool {
return nums[i] >= 6
})
fmt.Println("first >= 6 at index:", i)
}Das erste Element oberhalb eines Werts finden
Da sort.Search die Grenze findet, an der eine Bedingung zu true wechselt, eignet es sich hervorragend für Abfragen wie „Finde den ersten Wert, der größer als ein Schwellenwert ist“.
package main
import (
"fmt"
"sort"
)
func main() {
scores := []int{10, 20, 30, 40}
i := sort.Search(len(scores), func(i int) bool {
return scores[i] > 25
})
fmt.Println("first > 25:", scores[i])
}Zuerst muss sortiert werden
Eine binäre Suche setzt eine Reihenfolge voraus. Wenn das Slice nicht sortiert ist, sind die Ergebnisse bedeutungslos. Sortieren Sie immer vor der Suche.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{9, 1, 5, 3}
sort.Ints(nums)
i := sort.SearchInts(nums, 5)
fmt.Println(nums, "-> index of 5:", i)
}Deutlicher Performance-Gewinn
Bei einem Slice mit einer Million Elementen muss eine lineare Suche möglicherweise eine Million Elemente prüfen, eine binäre Suche dagegen etwa 20. Die einmaligen Sortierkosten machen sich bei vielen Suchen bezahlt.
Die passende Suchhilfe wählen
Zusammenfassung:
sort.SearchInts/SearchStrings/SearchFloat64s– typisierte Slicessort.Search– eigene Bedingung für beliebige indizierbare Daten
Kurzer Test
Sie rufen sort.SearchInts(s, 4) für ein sortiertes Slice auf, das 4 nicht enthält. Was wird zurückgegeben?
Zusammenfassung
Sortierte Daten mit einer binären Suche durchsuchen:
- Die Daten müssen zuerst sortiert werden
- Hilfsfunktionen geben einen Index oder eine Einfügeposition zurück
- Bestätigen Sie Treffer mit einem Gleichheitsvergleich
sort.Searchverarbeitet eigene Bedingungen
Häufig gestellte Fragen
Ist die Lektion „Sortierte Daten durchsuchen“ kostenlos?
Ja — der vollständige Text von „Sortierte Daten durchsuchen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Go Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Go Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Sortierte Daten durchsuchen“?
Binärsuche Du übst Go Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Go Academy zu starten?
Keine Vorkenntnisse erforderlich. Go Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Sortierte Daten durchsuchen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Go Academy-Lektion Code schreiben und ausführen?
Ja. Jede Go Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Slices sortieren
- Benutzerdefinierte Sortierreihenfolgen
- Sortierte Daten durchsuchen
- Stabiles Sortieren