3, 7, 12, 15, 18, 23, 25, 26, 30
Supposons que vous souhaitiez en trouver 25 à partir d'un certain nombre de colonnes organisées par ordre croissant, telles que.
La recherche linéaire est une méthode de recherche depuis le début dans l'ordre indiqué ci-dessous.
a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
HowManyLoops = 0
for i in a:
if i == 25:
break
HowManyLoops += 1
print('a[{}]C'est dedans.'.format(HowManyLoops))
a[6]C'est dedans.
Ensuite, voyons comment faire une dichotomie. Comme son nom l'indique, la dichotomie est une méthode de réduction du nombre d'éléments à examiner lors de la dichotomie. La méthode est la suivante.
Dans cet exemple, il s'est terminé avec seulement deux recherches. Voyons cela dans le code.
a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
pl = 0
pr = len(a)-1
HowManyLoops = 0
while True:
HowManyLoops += 1
pc = (pl + pr) // 2
if a[pc] > 25:
pr = pc - 1
elif a[pc] < 25:
pl = pc + 1
else:
print('a[{}]C'est dedans.'.format(pc))
break
if pr < pl:
print('La recherche a échoué.')
break
print('La boucle est{}Il y avait des moments.'.format(HowManyLoops))
a[6]C'est dedans.
Il y avait deux boucles.
De cette façon, nous avons pu rechercher en deux boucles. Je vais expliquer un peu la source. Les points sont pl, qui représente l'index le plus à gauche du tableau que vous regardez, pr, qui représente l'index le plus à droite, et pc, qui représente le milieu. Si l'élément que vous souhaitez rechercher se trouve sur le côté droit de pc (pc <élément que vous souhaitez rechercher), définissez pc + 1 sur pl, et si l'élément que vous souhaitez rechercher se trouve sur le côté gauche de pc (élément pc> que vous souhaitez rechercher), définissez pc-1 sur pr. Considérez un nouveau sous-tableau. De cette manière, le nombre d'éléments dans le sous-tableau d'intérêt est divisé en deux. Et si vous trouvez que pc est l'élément que vous souhaitez rechercher après l'avoir divisé en deux, la recherche sera réussie.
Jusqu'à présent, nous avons vu le cas d'une recherche réussie, mais qu'en est-il du cas d'une recherche infructueuse? En termes de source
if pr < pl:
print('La recherche a échoué.')
break
C'est la partie de. À propos, cette partie est un processus dont la recherche échoue lorsque l'index le plus à gauche du tableau partiel dépasse l'index le plus à droite. Pour voir cela, le tableau ci-dessus
a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
# 0 1 2 3 4 5 6 7 8
Jetons un coup d'œil aux étapes pour rechercher le nombre de à 27. Bien sûr, il n'y a pas de 27 dans ce tableau, donc la recherche échouera.
--Comparer les éléments 18 et 27 de l'indice 4 au milieu (pl = 0, pr = 8, pc = 4)
Que le nombre d'éléments dans le tableau d'origine soit pair ou impair, le nombre d'éléments dans le sous-tableau d'intérêt sera un nombre pair après la première recherche, donc fondamentalement, le flux de recherche ne changera pas. Dans le modèle d'échec de recherche, pl = pr = pc lors de la saisie de la dernière boucle, c'est-à-dire que le nombre d'éléments dans le sous-tableau est de 1. Par conséquent, si l'élément que vous souhaitez rechercher est plus grand que ce dernier élément, pl = pc + 1, et s'il est plus petit, pr = pc-1, pl dépassera pr. Il casse à ce moment.
Recommended Posts