Wyszukiwanie posortowanych danych
Wyszukiwanie binarne
Wyszukiwanie posortowanych danych to bezpłatna lekcja Go Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Go Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Go Academy zawiera 4 lekcji w sumie.
Dlaczego przeszukiwać posortowane dane
Po posortowaniu wycinka można znajdować elementy znacznie szybciej za pomocą wyszukiwania binarnego zamiast sprawdzać każdy element po kolei.
Pakiet sort w Go udostępnia funkcje pomocnicze do wyszukiwania, które działają w czasie logarytmicznym.
Wyszukiwanie liniowe kontra binarne
Wyszukiwanie liniowe sprawdza każdy element po kolei (O(n)). Wyszukiwanie binarne przy każdym kroku zmniejsza zakres wyszukiwania o połowę (O(log n)), ale wymaga wcześniejszego posortowania danych.
sort.SearchInts
sort.SearchInts znajduje indeks, pod którym znajduje się dana wartość, lub pod którym należałoby ją wstawić, aby wycinek pozostał posortowany. Wycinek musi być już posortowany rosnąco.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Potwierdzanie dopasowania
SearchInts zwraca indeks nawet wtedy, gdy danej wartości nie ma w wycinku — jest to punkt wstawienia. Zawsze potwierdzaj dopasowanie, sprawdzając 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)
}Punkt wstawienia
Gdy brakuje danej wartości, zwrócony indeks wskazuje dokładnie miejsce, w którym można ją wstawić, aby zachować sortowanie. W tym przypadku 4 trafiłoby na 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 działa tak samo dla posortowanego wycinka napisów.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}Ogólna funkcja sort.Search
sort.Search to elastyczny fundament wyszukiwania. Przekazuje się jej długość oraz funkcję f, która najpierw zwraca false, a następnie true; funkcja zwraca najmniejszy indeks, dla którego f ma wartość 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)
}Znajdowanie pierwszego elementu powyżej
Ponieważ sort.Search znajduje granicę, przy której warunek zmienia wartość na true, świetnie nadaje się do zapytań takich jak znalezienie pierwszej wartości większej od progu.
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])
}Najpierw trzeba posortować dane
Wyszukiwanie binarne zakłada uporządkowanie danych. Jeśli wycinek nie jest posortowany, wyniki są bezwartościowe. Zawsze sortuj dane przed wyszukiwaniem.
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)
}Zysk wydajności
W wycinku zawierającym milion elementów wyszukiwanie liniowe może sprawdzić milion elementów, podczas gdy binarne sprawdzi ich około 20. Koszt jednorazowego sortowania zwraca się przy wielu wyszukiwaniach.
Wybór funkcji pomocniczej do wyszukiwania
Podsumowanie:
sort.SearchInts/SearchStrings/SearchFloat64s- wycinki określonych typówsort.Search- niestandardowy warunek dla dowolnych danych dostępnych za pomocą indeksu
Szybkie sprawdzenie
Wywołują Państwo sort.SearchInts(s, 4) dla posortowanego wycinka, który nie zawiera 4. Co zostanie zwrócone?
Podsumowanie
Wyszukiwanie posortowanych danych za pomocą wyszukiwania binarnego:
- Dane muszą być najpierw posortowane
- Funkcje pomocnicze zwracają indeks lub punkt wstawienia
- Dopasowania należy potwierdzać sprawdzeniem równości
sort.Searchobsługuje niestandardowe warunki
Ucz się Go dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 51
- Lekcje
- 203
Często zadawane pytania
Czy lekcja „Wyszukiwanie posortowanych danych” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie posortowanych danych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Go Academy, przejdź na CoddyKit PRO. Kurs Go Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Wyszukiwanie posortowanych danych”?
Wyszukiwanie binarne Ćwiczysz Go Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Go Academy?
Nie wymagamy żadnego doświadczenia. Go Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Wyszukiwanie posortowanych danych”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Go Academy?
Tak. Każda lekcja Go Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie slice'ów
- Niestandardowe porządki sortowania
- Wyszukiwanie posortowanych danych
- Sortowanie stabilne