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;
}