====== 2021 - Sujet 30 - Exercice 2 ======

Soit ''T'' un tableau non vide d'entiers triés dans l'ordre croissant et ''n'' un entier.

La fonction ''chercher'', donnée ci-dessous doit renvoyer un indice où la valeur ''n'' apparaît éventuellement dans ''T'', et ''-1'' sinon.

Les paramètres de la fonction sont :
  * ''T'', le tableau dans lequel s'effectue la recherche ;
  * ''n'', l'entier à chercher dans le tableau ;
  * ''i'', l'indice de début de la partie du tableau où s'effectue la recherche ;
  * ''j'', l'indice de fin de la partie du tableau où s'effectue la recherche.

La fonction ''chercher'' est une fonction récursive basée sur le principe « diviser pour régner ».

Recopier et compléter le code de la fonction ''chercher'' proposée ci-dessous :

<code python linenums>
def chercher(T,n,i,j):
    assert 0 <= i and ...
    if i > j :
        return -1
    m = (i+j) // ???
    if T[m] < ??? :
        return chercher(T, n, ??? , ???)
    elif ??? :
        return chercher(T, n, ??? , ??? )
    else :
        return ???
</code>

L'exécution du code doit donner :

<code python>
>>> chercher([1,5,6,6,9,12],7,0,10)
AssertionError
>>> chercher([1,5,6,6,9,12],7,0,5)
-1
>>> chercher([1,5,6,6,9,12],9,0,5)
4
>>> chercher([1,5,6,6,9,12],6,0,5)
2
</code>