TL;DR
C'est un point fondamental, mais pour garder cela à l'esprit, j'écrirai le code de la dichotomie en Python et résumerai l'explication. ―― J'écrirai moi-même le code pour étudier (sans utiliser le module standard pour la dichotomie). ―― Étant donné que j'étais à l'origine diplômé d'une école dans le domaine du design, veuillez me pardonner tous les points intellectuellement compliqués dans le domaine de l'informatique.
La dichotomie est l'un des algorithmes permettant de trouver des valeurs dans un tableau trié. Aussi connu sous le nom de recherche binaire.
La condition est que le tableau cible de recherche a été trié, mais il a la propriété que la recherche est moins susceptible de ralentir même si la liste cible devient plus grande qu'une recherche normale.
La méthode consiste à obtenir d'abord la valeur située au centre de la liste, puis à comparer si la valeur au centre est plus grande ou plus petite que la valeur à rechercher.
Si la valeur à rechercher est inférieure à la valeur centrale du tableau, la plage du tableau est réduite du bord gauche à la plage avant la valeur centrale.
En revanche, si la valeur à rechercher est supérieure à la valeur centrale, la plage du tableau est réduite de la valeur un à droite de la valeur centrale à l'extrémité droite du tableau.
Après cela, la valeur centrale est prise dans la plage du tableau rétréci, il est à nouveau jugé si la valeur à rechercher est plus grande ou plus petite que la valeur centrale, et la séquence est réduite.
Si la valeur à rechercher correspond à la valeur au centre du tableau, cela signifie que la valeur à rechercher a été trouvée et la recherche se termine là.
Prenons le cas où vous recherchez la valeur de "2" dans la liste triée "[1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8]".
Commencez par obtenir la valeur au centre de la liste. La première valeur centrale est «4». La valeur "2" à rechercher est plus petite que la valeur centrale "4", donc réduisez la liste à gauche de la partie "4" et la valeur "[1, 1, 2, 3, 3]" À
Récupérez à nouveau la valeur centrale dans la liste restreinte. Cette fois, la valeur au centre de la liste est «2». Comme cela ne correspond pas au «2» de la cible de recherche, la recherche se termine lorsqu'il est déterminé que la cible existe.
Dans le processus de recherche normal, la recherche est effectuée pour voir s'ils correspondent dans l'ordre depuis le début. L'ordre de calcul est $ O (n) $ (cependant, si la valeur à rechercher existe au début, elle sera inférieure), et plus le nombre de séquences ($ n $) est grand, plus le temps de traitement linéaire est long. Cela deviendra.
Par contre, dans le cas d'une recherche dichotomique, l'ordre de calcul est $ O (log_2 n) $, donc même si la taille du tableau devient grande, le temps de traitement sera gonflé.
Bien qu'une recherche dichotomique soit plus rapide qu'une recherche normale, elle ne peut être utilisée qu'avec un tableau trié pour une recherche dichotomique (à moins qu'elle ne soit triée, la relation de grandeur sera étrange lors du fractionnement du tableau. ).
Par conséquent, dans le cas où le tableau cible de la recherche n'est pas trié et la recherche est exécutée une seule fois, le coût de calcul du tri est plus élevé que celui de la recherche normale, et le mérite d'utiliser la dichotomie est Il n'y en a pas.
D'un autre côté, si le tableau a déjà été trié, ou si le processus de recherche est répété plusieurs fois, le coût du calcul peut être réduit en utilisant la dichotomie même si le tri est exécuté.
Vous pouvez utiliser la dichotomie pour une liste de caractères ainsi qu'une valeur numérique, mais cette fois nous allons procéder comme un exemple avec une liste qui stocke des entiers.
De plus, au lieu de contrôler pour renvoyer l'index du résultat de la recherche, nous vérifierons simplement si la liste contient des valeurs.
from typing import List
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
def binary_search(sorted_list: List[int], search_value: int) -> bool:
"""
Effectuez une dichotomie pour voir si la valeur que vous recherchez est incluse dans la liste
Obtenez la valeur booléenne.
Parameters
----------
sorted_list : list of int
Une liste contenant des valeurs entières triées.
search_value : int
La valeur à rechercher.
Returns
-------
value_exists : bool
Si la valeur est incluse dans la liste.
"""
left_index: int = 0
right_index: int = len(sorted_list) - 1
while left_index <= right_index:
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
if search_value < middle_value:
right_index = middle_index - 1
continue
if search_value > middle_value:
left_index = middle_index + 1
continue
return True
return False
Je vais toucher le code dans l'ordre.
Tout d'abord, dans la dichotomie, la liste cible doit être triée, donc la fonction triée est utilisée pour trier la liste (la méthode de tri, etc. ne change pas).
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
Vient ensuite le traitement de la fonction de dichotomie.
left_index: int = 0
right_index: int = len(sorted_list) - 1
Les variables de gestion de la plage d'index de la liste cible sont définies comme left_index et right_index. L'index le plus à gauche de la liste est left_index et l'index le plus à droite est right_index. Ces valeurs seront mises à jour sur un côté chaque fois qu'elles sont coupées en deux jusqu'à ce que la boucle termine la recherche.
while left_index <= right_index:
Le processus de division en deux est exécuté à plusieurs reprises dans une boucle while. Cette boucle se répète tant que l'index le plus à gauche est à gauche de l'index le plus à droite ou a le même entier. S'il se trouve à droite de l'index à l'extrémité droite, la plage de la liste cible a disparu (toutes les cibles ont été recherchées), donc la boucle est terminée et il est jugé que la cible n'a pas été trouvée. ..
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
À l'intérieur de la boucle, middle_index stocke la valeur du milieu dans la plage de tableau cible. Divisez par 2 par «// 2» et tronquez la fraction («//» se comporte comme un étage en plus de la division).
Il fait également référence à cet index ainsi qu'à l'index central et définit la valeur centrale sur la variable (middle_value).
if search_value < middle_value:
right_index = middle_index - 1
continue
Dans l'instruction if, si la valeur à rechercher est inférieure à la valeur centrale, le tableau est divisé en seulement la moitié gauche, de sorte que l'index le plus à droite (right_index) est placé à gauche de l'index central (`middle_index --1". »).
if search_value > middle_value:
left_index = middle_index + 1
continue
En revanche, si la valeur à rechercher est supérieure à la valeur centrale, ajustez la valeur de l'index le plus à gauche (left_index) pour que le tableau ne soit que la moitié droite.
return True
Si la valeur à rechercher n'est ni plus petite ni plus grande que la valeur centrale, c'est-à-dire si elle est identique à la valeur centrale, True est renvoyé car la valeur à rechercher existe.
return False
Je vais vraiment l'exécuter. Tout d'abord, essayez à partir de la condition que la cible existe dans la liste.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=83)
print(value_exists)
True
True est renvoyé normalement. Ensuite, essayez de spécifier les conditions selon lesquelles la cible de recherche n'est pas incluse dans la liste.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=84)
print(value_exists)
False
Ceci est également faux comme prévu.
Recommended Posts