Rechercher dans des données triées
Effectuer une recherche binaire
Rechercher dans des données triées est une leçon Go Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Go Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Go Academy comprend 4 leçons au total.
Pourquoi rechercher des données triées
Une fois une tranche triée, vous pouvez trouver des éléments beaucoup plus rapidement avec une recherche binaire plutôt qu'en examinant chaque élément.
Le package sort de Go fournit des fonctions auxiliaires de recherche qui s'exécutent en temps logarithmique.
Recherche linéaire ou binaire
Une recherche linéaire vérifie chaque élément l'un après l'autre (O(n)). Une recherche binaire divise la plage de recherche par deux à chaque étape (O(log n)), mais exige que les données soient d'abord triées.
sort.SearchInts
sort.SearchInts trouve l'indice où se trouve une valeur ou celui où elle devrait être insérée pour conserver la tranche triée. La tranche doit déjà être triée par ordre croissant.
package main
import (
"fmt"
"sort"
)
func main() {
nums := []int{1, 3, 5, 7, 9}
i := sort.SearchInts(nums, 5)
fmt.Println("index:", i)
}Confirmer une correspondance
SearchInts renvoie un indice même si la valeur est absente, à savoir le point d'insertion. Vérifiez toujours la correspondance avec 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)
}Point d'insertion
Lorsqu'une valeur est absente, l'indice renvoyé indique exactement où vous devriez l'insérer pour conserver l'ordre. Ici, 4 serait placé à l'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 fait la même chose pour une tranche de chaînes triée.
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"apple", "cherry", "mango"}
i := sort.SearchStrings(words, "cherry")
fmt.Println("index:", i)
}La fonction générale sort.Search
sort.Search est le cœur flexible de la recherche. Vous lui fournissez une longueur et une fonction f qui renvoie d'abord false, puis true ; il renvoie le plus petit indice où f est vraie.
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)
}Trouver le premier élément supérieur
Comme sort.Search trouve la frontière où la condition devient vraie, il convient parfaitement aux requêtes telles que « trouver la première valeur supérieure à un seuil ».
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])
}Trier d'abord
La recherche binaire suppose que les éléments sont ordonnés. Si la tranche n'est pas triée, les résultats n'ont aucun sens. Triez toujours avant d'effectuer la recherche.
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)
}Gain de performance
Pour une tranche d'un million d'éléments, une recherche linéaire peut en examiner un million, tandis qu'une recherche binaire en examine environ 20. Le coût du tri initial est amorti sur de nombreuses recherches.
Choisir le bon outil de recherche
Résumé :
sort.SearchInts/SearchStrings/SearchFloat64s- tranches spécialiséessort.Search- condition personnalisée sur des données indexables de tout type
Vérification rapide
Vous appelez sort.SearchInts(s, 4) sur une tranche triée qui ne contient pas 4. Que renvoie cette fonction ?
Récapitulatif
Rechercher dans des données triées avec une recherche binaire :
- Les données doivent d'abord être triées
- Les fonctions auxiliaires renvoient un indice ou un point d'insertion
- Confirmez les correspondances avec un test d'égalité
sort.Searchgère les conditions personnalisées
Questions Fréquemment Posées
La leçon « Rechercher dans des données triées » est-elle gratuite ?
Oui — le texte complet de « Rechercher dans des données triées » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Go Academy, passe à CoddyKit PRO. Le cours Go Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Rechercher dans des données triées » ?
Effectuer une recherche binaire Tu pratiques Go Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Go Academy ?
Aucune expérience préalable n'est requise. Go Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Rechercher dans des données triées » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Go Academy ?
Oui. Chaque leçon Go Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Trier des slices
- Ordres de tri personnalisés
- Rechercher dans des données triées
- Tri stable