Comment implémenter l'algorithme de recherche binaire dans Go
Recherche binaireest un algorithme simple pour trouver un élément dans untableau trié, et il est généralement référencé comme un exemple de code à étudier lors de l'apprentissage d'un nouveau langage de programmation.
Efficacité
C'est très efficace:
- Temps:O (log n), c'est au pire logaritmique
- Espacer:0(1), prend un temps constant
Théorie
Étant donné un tableau trié, nous choisissons l'élément Y au milieu et nous le comparons à la valeur cible X.
Si Y correspond à X, nous retournons la position Y et nous sortons.
Nous déterminons si X <Y, dans ce cas, nous écartons le côté droit, et nous allons au milieu du côté gauche, et nous répétons la même opération que ci-dessus.
La recherche se termine lorsque Y correspond finalement à X. Si cela ne se produit pas, nous retournons la position que X aurait prise s'il était dans le tableau.
Mise en œuvre
Nous avons de la chance, la bibliothèque standard Go fournit une implémentation d'arbre binaire dans sonsort
paquet, danssort.Search()
.
Voyons l'utilisation de l'API, telle qu'elle est extraite de la documentation du package, afin que nous sachions quoisort.Search
devrait retourner:
package main
import (
“fmt”
“sort”
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
<span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">sort</span>.<span style="color:#a6e22e">Search</span>(len(<span style="color:#a6e22e">a</span>), <span style="color:#66d9ef">func</span>(<span style="color:#a6e22e">i</span> <span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">bool</span> { <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">>=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> < len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&&</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">==</span> <span style="color:#a6e22e">x</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"found %d at index %d in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">i</span>, <span style="color:#a6e22e">a</span>)
} <span style="color:#66d9ef">else</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"%d not found in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">a</span>)
}
}
sort.Search
renvoie un indexi
, et nous devons simplement nous assurer que cet index contient réellementx
.
Bien sûr, nous voulons savoir comment cela est mis en œuvre en interne. Étant donné que la bibliothèque standard est écrite en Go et en open source, il est vraiment facile de voir commentsort.Search
est implémenté:
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := i + (j-i)/2 // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
Décomposons-le:
Étant donné un tableau de longueurn
, et une fonction de comparaisonf
(qui évalue en internex >= a[h]
), nous commençons à itérer le tableaua
.
Utilisons les valeurs réelles que nous utilisons dans l'exemple, il est plus facile de montrer ce qui se passe.
Données:
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
Itération 1:
i
est0
,j
est9
.h
est calculé comme(0 + (9-0) / 2)
=4
a[h]
est15
. Cela signifie que nous exécutonsj = h
Itération 2:
i
est0
,j
est4
.h
est calculé comme(0 + (4-0) / 2)
=2
a[h]
est6
. Nous avons trouvé la position dex
, cela signifie que nous retournonsh = 2
Recherche dans l'ordre inverse
Puisque nous pouvons passer une fonction àsort.Search
, il est facile de rechercher sur un tableau trié dans l'ordre inverse, comme
a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6
en passant une fonction qui comparea[i] <= x
au lieu dea[i] >= x
.
i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
Plus de tutoriels go:
- Utilisation du proxy inverse NGINX pour servir les services Go
- Faire une copie d'une structure dans Go
- Les bases d'un serveur Web Go
- Trier un type de carte dans Go
- Allez les pointeurs en un mot
- Go Tags expliqué
- Aller au formatage de la date et de l'heure
- Traitement JSON avec Go
- Fonctions Go Variadic
- Fiche de triche Go Strings
- L'interface Go Empty expliquée
- Débogage Go avec VS Code et Delve
- Named Go renvoie des paramètres
- Générer des nombres et des chaînes aléatoires dans Go
- Structure du système de fichiers d'un projet Go
- Algorithme de recherche binaire implémenté dans Go
- Utilisation des indicateurs de ligne de commande dans Go
- GOPATH a expliqué
- Créez une application de ligne de commande avec Go: lolcat
- Création d'une commande CLI avec Go: cowsay
- Utilisation de Shell Pipes avec Go
- Tutoriel Go CLI: Clone de fortune
- Lister les fichiers dans un dossier avec Go
- Utilisez Go pour obtenir une liste des référentiels à partir de GitHub
- Allez, ajoutez une tranche de chaînes à un fichier
- Allez, convertissez une chaîne en une tranche d'octets
- Visualisez vos contributions Git locales avec Go
- Premiers pas avec Go CPU et profilage de la mémoire
- Résolution de l'erreur "ne prend pas en charge l'indexation" dans un programme Go
- Mesure du temps d'exécution dans un programme Go
- Création d'un robot d'exploration Web avec Go pour détecter les titres en double
- Go Best Practices: pointeur ou récepteurs de valeur?
- Go Best Practices: Devez-vous utiliser une méthode ou une fonction?
- Go Structures de données: définir
- Aide-mémoire Go Maps
- Générer des implémentations pour les types génériques dans Go
- Go Data Structures: Dictionnaire
- Structures de données Go: table de hachage
- Implémenter des écouteurs d'événements dans Passer par les canaux
- Go Structures de données: pile
- Go Structures de données: file d'attente
- Go Structures de données: arbre de recherche binaire
- Go Structures de données: graphique
- Structures de données Go: liste liée
- Le guide complet des structures de données Go
- Comparaison des valeurs Go
- Est-ce que Go est orienté objet?
- Travailler avec une base de données SQL dans Go
- Utilisation des variables d'environnement dans Go
- Tutoriel Go: API REST soutenue par PostgreSQL
- Activation de CORS sur un serveur Web Go
- Déployer une application Go dans un conteneur Docker
- Pourquoi Go est un langage puissant à apprendre en tant que développeur PHP
- Allez, supprimez le caractère de nouvelle ligne io.Reader.ReadString
- Allez, comment observer les changements et reconstruire votre programme
- Allez, comptez les mois depuis une date
- Accéder aux paramètres HTTP POST dans Go