Recherche dichotomique

En informatique, rechercher un élément dans un tableau est un problème récurant et parfois coûteux. Nous allons voir ici une méthode simple permettant de trouver une élément dans un tableau trié et grace à cette propriété nous allons voir comment diminuer drastiquement le nombre d'itération nécéssaire. On peu donc écrire cette première propriété :

• (1) ∀ i,j ∈ [0,,N] | i<j ∧ T[i] < T[j] ⇒ triée

La recherche dichotomique consiste à diviser l'espace de recherche. (valeur = valeur recherchée). En effet, il en résulte que, grâce à la propriété (1) si T[i]<valeur alors la propriété (1) induit nouvelle propriété (2). Il en résulte également que si T[x]>valeur alors la propriété (1) induit la propriété (3). Que l'on peu réécrire :

• (2) { ∀ y ∈ [0..x], T[y]<valeur ∧ ∃ w ∈]x..N] | T[y] = valeur }
  
  • la valeur ce trouve dans le sous-enssemble de gauche
• (3) { ∀ y ∈ [x..N], T[y]>valeur ∧ ∃ w ∈ [0..x[ | T[w]=valeur }
  
  • la valeur ce trouve dans le sous-enssemble de droite

En excluant une des deux parties à chaque itération le nouvel ensemble est soumis à la même propriété (1) qui induis (2) et (3). L'algorithme prend si possible le milieux comme point de comparaison (T[x]) pour exclure la partie la plus grande possible à chaque itération ($N/2+1$), on peut extraire les sous-propriété (4) et (5) du nouvel ensemble :

• (4) { ∃w ∈ [0..N] | T[w]=valeur }
  • la valeur existe dans l'intervale
• (5) { card(U) < card(E) }
  • la taille du sous-enssemble diminue

Finalement le tableau est vu comme un arbre de recherche où chaque itération élimine une branche droite ou gauche et son sommet :

Implementation

template<class T>
inline long dichotomicsearch(const T* array, size_t size, T val) noexcept
{
    size_t start = 0, end = size-1;
    size_t mid = (start+end)/2;

    // the input array must be sorted
    assert(std::is_sorted(array, array+size)); // (1)

    if(array[0] == val)
        return 0;
    // exclude [0] and [end] for performance & assertion test
    if(array[size-1] == val)
        return size-1;

    while(start <= end && array[mid] != val)
    {
        long diff = val-array[mid];
        bool iv = (diff < 0)*(~0); // 1111..1111 si diff<0 sinon 0000.0000
        bool ni = ~iv;                   // 0000..0000 si diff>=0 sinon  1111..1111

        // the new subset is reduced on each iteration until the element is found
        // otherwise the size of the subset become negative, so the element isn’t on the list (exit)
        assert((iv&(mid+1)) + (start&ni) + (ni&(mid-1)) + (end&iv) < start+end); // (5)

        start = (iv&(mid+1)) | (start&ni); //<=> if(diff < 0) start = mid+1
        end =   (ni&(mid-1)) | (end&iv);  //<=> if(diff >= 0) end = mid-1;
        mid = (start+end)/2;

        // each excluded subset does not contain @val
        // by equivalence this assertion this equals to say:
        //       all element of the left subset doesn't contain @val
        //       and  the subset is sorted so max(left)<@val & min(right)>@val
        // idem for the right subset

        assert(*std::max_element(array, array+start) < val); // (2)
        assert(*std::min_element(array+end, array+size-1) > val); // (3)
        // so val is on the subspace [start-end]
        assert(std::binary_search(array+start, array+end, val) != -1); // (4)
    }

    return array[mid] == val ? mid : -1;
}