rechdicho.py

Created on June 25, 2019

862 Bytes

Effectue une recherche dichotomique de x dans le tableau T.

#!/usr/bin/env python3

# fichier : rech.py
#  auteur : Pascal CHAUVIN
#    date : 2019-06-25

"""
Recherche (dichotomique) de la valeur x dans le tableau T :

T est un tableau
x est un nombre

La fonction rend le rang de x dans le tableau, si x est present 
dans le tableau, et la valeur "None" (aucun) sinon.
"""

def recherche(T, x):
  i = 0
  j = len(T) - 1
  m = None

  p = 0

  while (i <= j) and (m is None):
    p += 1
    print("p={}, i={}, j={}, j-i={}".format(p, i, j, j-i))
    k = (i + j) // 2
    if T[k] == x:
      m = k
    else:
      if T[k] < x:
        i = k + 1
      else:
        j = k - 1
  return m



import random

T = [random.randint(0, 100) for _ in range(20)]
#T = sorted([random.randint(0, 100) for _ in range(20)])
#T = []
x = random.randint(0, 100)

print(T)
print(x)
print("indice={}".format(recherche(T, x)))