PricingLoginStart free
Go Academy · leksjon

Søke i sorterte data

Binærsøk

Leksjon 3 av 413 trinn

Søke i sorterte data er en gratis leksjon i Go Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Go Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Go Academy inneholder totalt 4 leksjoner.

Hvorfor søke i sorterte data

Når en slice er sortert, kan du finne elementer langt raskere med binærsøk enn ved å skanne hvert element.

Gos sort-pakke tilbyr hjelpefunksjoner for søk som kjører på logaritmisk tid.

Lineært kontra binært

Et lineært søk kontrollerer hvert element ett etter ett (O(n)). Et binærsøk halverer søkeområdet for hvert trinn (O(log n)), men krever at dataene er sortert først.

sort.SearchInts

sort.SearchInts finner indeksen der en verdi ligger, eller der den må settes inn for at slicen fortsatt skal være sortert. Slicen må allerede være sortert i stigende rekkefølge.

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7, 9}
	i := sort.SearchInts(nums, 5)
	fmt.Println("index:", i)
}

Bekrefte et treff

SearchInts returnerer en indeks selv om verdien mangler, altså innsettingspunktet. Bekreft alltid ved å 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)
}

Innsettingspunkt

Når en verdi mangler, er den returnerte indeksen nøyaktig stedet der du ville satt den inn for å beholde sorteringen. Her skal 4 plasseres på 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)
}

SearchStrings

sort.SearchStrings gjør det samme for en sortert slice med strenger.

package main

import (
	"fmt"
	"sort"
)

func main() {
	words := []string{"apple", "cherry", "mango"}
	i := sort.SearchStrings(words, "cherry")
	fmt.Println("index:", i)
}

Det generelle sort.Search

sort.Search er den fleksible kjernen. Du oppgir en lengde og en funksjon f som først er false og deretter true; den returnerer den minste indeksen der f er true.

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)
}

Finn første element over

Fordi sort.Search finner grensen der betingelsen går over til true, er den godt egnet til spørsmål som «hva er den første verdien som er større enn en terskel?»

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])
}

Må sorteres først

Binærsøk forutsetter en rekkefølge. Hvis slicen ikke er sortert, er resultatene meningsløse. Sorter alltid før du søker.

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)
}

Ytelsesgevinst

For en slice med én million elementer kan et lineært søk kontrollere én million elementer, mens et binærsøk kontrollerer omtrent 20. Kostnaden ved å sortere én gang lønner seg ved mange søk.

Velge riktig søkehjelp

Oppsummering:

  • sort.SearchInts / SearchStrings / SearchFloat64s - typespesifikke slices
  • sort.Search - egendefinert betingelse for alle data som kan indekseres

Hurtigsjekk

Du kaller sort.SearchInts(s, 4) på en sortert slice som ikke inneholder 4. Hva returnerer den?

Besvar den i den interaktive leksjonen

Oppsummering

Søk i sorterte data med binærsøk:

  • Dataene må sorteres først
  • Hjelpefunksjonene returnerer en indeks eller et innsettingspunkt
  • Bekreft treff med en likhetssjekk
  • sort.Search håndterer egendefinerte betingelser
Gratis å komme i gang

Lær deg Go med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
51
Leksjoner
203
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «Søke i sorterte data» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien Go Academy, inkludert «Søke i sorterte data», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i Go Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Søke i sorterte data»?

Binærsøk Du øver på Go Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Go Academy?

Ingen tidligere erfaring er nødvendig. Go Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «Søke i sorterte data»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Go Academy-leksjonen?

Ja. Alle Go Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. Sortere slices
  2. Egendefinerte sorteringsrekkefølger
  3. Søke i sorterte data
  4. Stabil sortering
← Tilbake til Go Academy