====== Recherche dichotomique ======

On fournit un tableau d'items.

<WRAP box>
**Besoin :** pour une valeur ''needle'' donnée, chercher l'indice de sa première occurrence dans le tableau, si elle s'y trouve, sinon -1.

**Précondition :** un critère d'ordre est défini et le tableau doit être trié dans l'ordre croissant.

**Principe :** Le tableau contient ''n = len(tableau)'' items. les indices vont de ''0'' à ''n - 1''.
  * On initialise ''a'' à ''0'' et ''b'' à ''n - 1''.
  * Nous faisons en sorte que si ''needle'' est dans le tableau, sa première occurrence est toujours entre ''a'' et ''b'' (ce qui est vrai avec les valeurs initiales de ''a'' et ''b'')
  * Nous faisons aussi en sorte que l'écart ''b - a'' se réduise d'au moins 1 à chaque étape de sorte que l'écart ''b - a'' finit forcément par être nul.
  * Les deux éléments précédents font qu'à la fin, si ''needle'' est dans le tableau, sa première occurrence est forcément ''a'' -- la valeur de ''a'' finale. 

Voyons comment nous faisons évoluer ''a'' et ''b'' :
  * On lit la valeur du tableau à l'indice au milieu entre ''a'' et ''b'' : en ''%%i_m = (a + b)//2%%''.
  * Si cette ''valeur >= needle'' cela signifie que  la première occurrence de ''needle'' est forcément sur la gauche de ''i_m'' ou éventuellement en ''i_m''. On peut donc continuer à chercher sur ''[a;i_m]'' et donc on décide que : ''b = i_m''\\ <wrap important>On sait que ''i_m < b'', en choisissant ''b = i_m'' on réduit ''b'' d'au moins 1 et donc ''b - a'' aussi.</wrap>
  * Sinon, cela signifie que ''valeur < needle'' et que ''needle'' est strictement à droite de ''i_m''. On peut donc continuer à chercher dans ''[i_m + 1 ; b]]''. On décide donc ''a = i_m + 1''\\ <wrap important>Si on se contentait de ''a = i_m'', dans certains cas ''a'' ne changerait pas et donc ''b - a'' ne diminuerait plus, ce qui ferait  une boucle infinie.</wrap> 
</WRAP>

**Exemple :**

<code python>
tableau = [5, 7, 19, 21, 45, 45, 74]
n = len(tableau) # n = 7
needle = 45 # needle = aiguille, la valeur cherchée

# a et b délimitent la zone de recherche.
# On commence avec les bords du tableau : [0 ; 6]
a, b = 0, 6
i_m = (a + b) // 2 # i_m = 3

tableau[i_m] < needle # car tableau[i_m] = 21
# on peut continuer strictement sur la moitié droite
a = i_m + 14 # a passe à 4. La recherche continue sur [4 ; 6]

i_m = (a + b) // 2 # i_m = 5
tableau[i_m] >= needle # car tableau[i_m] = 45
# on peut continuer à gauche de 5
b = i_m # recherche continue sur [4;5]

i_m = (a + b) // 2 # i_m = 4
tableau[i_m] >= needle # car tableau[i_m] = 45
b = i_m # recherche continue sur [4;4]

# a == b pas besoin d'aller plus loin
# puisque tableau[a] == 45 == needle, la réponse est a = 4
</code>

<WRAP tip>La recherche de l'exemple s'est faite en 3 étapes ce qui correspond au fait que $7 < 2^3$. Si le tableau contenait $n = 1\,000\,000 < 2^{20}$ items, 20 étapes suffiraient.</WRAP>

<WRAP box>**À faire**\\ Implémenter en Python un algorithme de recherche par dichotomie.</WRAP>