Cercare dati ordinati
Ricerca binaria
Cercare dati ordinati è una lezione Go Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Go Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Go Academy include 4 lezioni in totale.
Perché cercare dati ordinati
Una volta ordinata una slice, può trovare gli elementi molto più rapidamente utilizzando la ricerca binaria invece di analizzare ogni elemento.
Il package sort di Go fornisce helper di ricerca con complessità logaritmica.
Ricerca lineare e binaria
Una ricerca lineare controlla ogni elemento uno alla volta (O(n)). La ricerca binaria dimezza l'intervallo di ricerca a ogni passaggio (O(log n)), ma richiede che i dati siano prima ordinati.
sort.SearchInts
sort.SearchInts trova l'indice in cui si trova un valore o in cui dovrebbe essere inserito per mantenere ordinata la slice. La slice deve essere già ordinata in modo crescente.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Confermare una corrispondenza
SearchInts restituisce un indice anche se il valore non è presente, cioè il punto di inserimento. Confermi sempre controllando 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)
}Punto di inserimento
Quando manca un valore, l'indice restituito indica esattamente dove inserirlo per mantenere l'ordinamento. In questo caso 4 andrebbe all'indice 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 fa lo stesso per una slice di stringhe ordinata.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}La sort.Search generale
sort.Search è il componente flessibile alla base della ricerca. Le si forniscono una lunghezza e una funzione f che restituisce prima false e poi true; la funzione restituisce il primo indice in cui f è vera.
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)
}Trovare il primo elemento superiore
Poiché sort.Search trova il confine in cui la condizione passa a true, è ideale per domande come «qual è il primo valore maggiore di una soglia?».
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])
}La slice deve essere ordinata prima
La ricerca binaria presuppone un ordine. Se la slice non è ordinata, i risultati non hanno significato. Ordini sempre prima di cercare.
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)
}Un vantaggio in termini di prestazioni
In una slice di un milione di elementi, una ricerca lineare può controllare un milione di elementi, mentre una ricerca binaria ne controlla circa 20. Il costo di un singolo ordinamento viene ammortizzato con molte ricerche.
Scegliere l'helper di ricerca
Riepilogo:
sort.SearchInts/SearchStrings/SearchFloat64s- slice tipizzatesort.Search- condizione personalizzata su dati indicizzabili di qualsiasi tipo
Verifica rapida
Chiama sort.SearchInts(s, 4) su una slice ordinata che non contiene 4. Che cosa restituisce?
Riepilogo
La ricerca binaria nei dati ordinati:
- I dati devono essere ordinati prima
- Gli helper restituiscono un indice o un punto di inserimento
- Le corrispondenze vanno confermate con un controllo di uguaglianza
sort.Searchgestisce condizioni personalizzate
Domande Frequenti
La lezione «Cercare dati ordinati» è gratuita?
Sì — il testo completo di «Cercare dati ordinati» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Go Academy, passa a CoddyKit PRO. Il corso Go Academy include 4 lezioni in totale.
Cosa imparerò in «Cercare dati ordinati»?
Ricerca binaria Eserciti Go Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Go Academy?
Non è richiesta alcuna esperienza precedente. Go Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Cercare dati ordinati»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Go Academy?
Sì. Ogni lezione Go Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ordinare gli slice
- Ordini di ordinamento personalizzati
- Cercare dati ordinati
- Ordinamento stabile