Algorithme de recherche binaire implémenté dans Go

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 sonsortpaquet, danssort.Search().

Voyons l'utilisation de l'API, telle qu'elle est extraite de la documentation du package, afin que nous sachions quoisort.Searchdevrait 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">&gt;=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&amp;&amp;</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.Searchrenvoie 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.Searchest 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:

iest0,jest9.
hest calculé comme(0 + (9-0) / 2)=4
a[h]est15. Cela signifie que nous exécutonsj = h

Itération 2:

iest0,jest4.
hest 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] <= xau lieu dea[i] >= x.