Søgning i sorterede data
Binær søgning
Søgning i sorterede data er en gratis Go Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i Go Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Go Academy-kurset indeholder 4 lektioner i alt.
Hvorfor søge i sorterede data
Når en slice er sorteret, kan du finde elementer langt hurtigere med binær søgning end ved at gennemgå hvert element.
Gos sort-pakke indeholder hjælpefunktioner til søgning, som kører i logaritmisk tid.
Lineær eller binær søgning
En lineær søgning kontrollerer hvert element ét ad gangen (O(n)). En binær søgning halverer søgeområdet ved hvert trin (O(log n)), men kræver, at dataene er sorteret først.
sort.SearchInts
sort.SearchInts finder det indeks, hvor en værdi findes, eller hvor den skal indsættes for at bevare slicens sortering. Slicen skal allerede være sorteret i stigende rækkefølge.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Bekræft et match
SearchInts returnerer et indeks, selv hvis værdien ikke findes, nemlig indsættelsespunktet. Bekræft altid resultatet ved at kontrollere 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)
}Indsættelsespunkt
Når en værdi mangler, er det returnerede indeks præcis det sted, hvor du skal indsætte den for at bevare sorteringen. Her skal 4 placeres ved indeks 2.
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)
}Søgning i strenge
sort.SearchStrings gør det samme for en sorteret slice med strenge.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}Den generelle sort.Search
sort.Search er den fleksible kerne. Du angiver en længde og en funktion f, der først returnerer false og derefter true. Funktionen returnerer det mindste indeks, hvor f er sand.
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)
}Find det første element over en grænse
Da sort.Search finder grænsen, hvor betingelsen skifter til sand, er den velegnet til forespørgsler som at finde den første værdi, der er større end en tærskel.
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])
}Dataene skal være sorteret først
Binær søgning forudsætter en rækkefølge. Hvis slicen ikke er sorteret, er resultaterne meningsløse. Sortér altid før søgning.
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)
}En gevinst i ydeevne
For en slice med én million elementer kan en lineær søgning kontrollere én million elementer, mens en binær søgning kontrollerer omkring 20. Det kan betale sig at sortere én gang, hvis du skal søge mange gange.
Vælg den rigtige søgehjælpefunktion
Opsummering:
sort.SearchInts/SearchStrings/SearchFloat64s– typespecifikke slicessort.Search– brugerdefineret betingelse for alle data, der kan indekseres
Hurtigt tjek
Du kalder sort.SearchInts(s, 4) på en sorteret slice, der ikke indeholder 4. Hvad returnerer den?
Opsummering
Søgning i sorterede data med binær søgning:
- Dataene skal være sorteret først
- Hjælpefunktionerne returnerer et indeks eller et indsættelsespunkt
- Bekræft matches med en lighedskontrol
sort.Searchhåndterer brugerdefinerede betingelser
Lær Go med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 51
- Lektioner
- 203
Ofte stillede spørgsmål
Er lektionen “Søgning i sorterede data” gratis?
Ja — alle 3 lektioner i læringssporet Go Academy, inklusive “Søgning i sorterede data”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Go Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Søgning i sorterede data”?
Binær søgning Du øver dig i Go Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Go Academy?
Der kræves ingen tidligere erfaring. Go Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Søgning i sorterede data”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Go Academy-lektion?
Ja. Alle Go Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Sortering af slices
- Brugerdefinerede sorteringsrækkefølger
- Søgning i sorterede data
- Stabil sortering