from random import shuffle, randint
import matplotlib.pyplot as plt

def rechercheDicho(liste, valeur, debutZoneRecherche, finZoneRecherche):
  """
  Fonction renvoyant l'indice d'une valeur si elle est présente dans liste,
  et renvoyant -1 sinon
  """
  if len(liste) == 0:
    return (-1,1)
  indiceMilieu = int((debutZoneRecherche+finZoneRecherche)/2)
  valeurMediane = liste[indiceMilieu]
  if valeurMediane == valeur:
    return (indiceMilieu,1)
  elif valeur < valeurMediane and indiceMilieu > debutZoneRecherche:
      retour = rechercheDicho(liste, valeur, debutZoneRecherche, indiceMilieu-1)
      return (retour[0], 1+retour[1])
  elif valeur > valeurMediane and indiceMilieu < finZoneRecherche:
      retour = rechercheDicho(liste, valeur, indiceMilieu+1, finZoneRecherche)
      return (retour[0], 1+retour[1])
  else:
    return (-1,1)

def rechercheNaive(liste, valeur):
    """
    Recheche Naive dans une liste triée.
    """
    for i in range(0, len(liste)):
        if liste[i] == valeur:
            return (i,i)
    return (-1,len(liste))

def evalAlgo(n):
    rec1 = 0
    rec2 = 0
    NB_TESTS = 100
    for i in range(0, NB_TESTS):
        liste = [x for x in range(0, n)]
        shuffle(liste)
        valeur = randint(0,n-1)
        rec1 += rechercheNaive(liste, valeur)[1]
        rec2 += rechercheDicho(liste, valeur, 0, n-1)[1]
    return (rec1/NB_TESTS, rec2/NB_TESTS)

NB_MAX = 500
abscisses = [n for n in range(1,NB_MAX)]
res = [evalAlgo(n) for n in abscisses]

ordonnees1 = list(map(lambda x: x[0], res))
ordonnees2 = list(map(lambda x: x[1], res))

plt.plot(abscisses, ordonnees1)
plt.plot(abscisses, ordonnees2)

plt.xlim(0, NB_MAX)
plt.ylim(0, NB_MAX)

plt.show()

print(res)