TL;DR
――Es ist ein grundlegender Punkt, aber um dies zu berücksichtigen, werde ich den Code für die Dichotomie in Python schreiben und die Erklärung zusammenfassen. ――Ich schreibe den Code selbst zum Lernen (ohne das Standardmodul für die Dichotomie zu verwenden). ―― Da ich ursprünglich Absolvent einer Schule im Bereich Design war, verzeihen Sie mir bitte alle intellektuell komplizierten Punkte im Bereich Informatik.
Die Dichotomie ist einer der Algorithmen zum Auffinden von Werten in einem sortierten Array. Wird auch als binäre Suche bezeichnet.
Die Bedingung ist, dass das Suchzielarray sortiert wurde, aber die Eigenschaft hat, dass die Suche weniger wahrscheinlich langsamer wird, selbst wenn die Zielliste größer als eine normale Suche wird.
Die Methode besteht darin, zuerst den Wert in der Mitte der Liste abzurufen und dann zu vergleichen, ob der Wert in der Mitte größer oder kleiner als der gesuchte Wert ist.
Wenn der zu durchsuchende Wert kleiner als der Mittelwert des Arrays ist, wird der Bereich des Arrays vom linken Rand bis zum Bereich vor dem Mittelpunkt eingegrenzt.
Wenn andererseits der zu durchsuchende Wert größer als der Mittelwert ist, wird der Bereich des Arrays vom Wert eins rechts vom Mittelwert bis zum rechten Ende des Arrays eingegrenzt.
Danach wird der Mittelwert im Bereich des eingegrenzten Arrays genommen, es wird erneut beurteilt, ob der zu durchsuchende Wert größer oder kleiner als der Mittelwert ist, und die Sequenz wird eingegrenzt.
Wenn der zu durchsuchende Wert mit dem Wert in der Mitte des Arrays übereinstimmt, bedeutet dies, dass der zu durchsuchende Wert gefunden wurde und die Suche dort endet.
Stellen Sie sich den Fall vor, in dem Sie in der sortierten Liste nach dem Wert "2" suchen [1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8] ".
Holen Sie sich zuerst den Wert in die Mitte der Liste. Der erste zentrale Wert ist "4". Der zu suchende Wert "2" ist kleiner als der Mittelwert "4". Grenzen Sie daher die Liste links neben dem Teil "4" und den Wert "[1, 1, 2, 3, 3]" ein Zu
Holen Sie sich den Mittelwert erneut in die verengte Liste. Diesmal ist der Wert in der Mitte der Liste "2". Da dies nicht mit der "2" des Suchziels übereinstimmt, endet die Suche, wenn festgestellt wird, dass das Ziel vorhanden ist.
Im normalen Suchvorgang wird die Suche durchgeführt, um festzustellen, ob sie von Anfang an in der richtigen Reihenfolge übereinstimmen. Die Berechnungsreihenfolge lautet $ O (n) $ (wenn jedoch der zu durchsuchende Wert zu Beginn vorhanden ist, ist er geringer). Je größer die Anzahl der Sequenzen ($ n $) ist, desto länger ist die lineare Verarbeitungszeit. Es wird werden.
Andererseits ist im Fall einer dichotomen Suche die Berechnungsreihenfolge $ O (log_2 n) $. Selbst wenn die Größe des Arrays groß wird, wird die Verarbeitungszeit aufgebläht.
Eine dichotome Suche ist zwar schneller als eine normale Suche, kann jedoch nur mit einem sortierten Array für eine dichotome Suche verwendet werden (sofern sie nicht sortiert ist, ist die Größenbeziehung beim Aufteilen des Arrays seltsam. ).
Daher sind in dem Fall, in dem das Suchzielarray nicht sortiert ist und die Suche nur einmal ausgeführt wird, die Berechnungskosten für die Sortierung höher als die für die normale Suche, und der Vorteil der Verwendung der Dichotomie ist Da ist gar nichts.
Wenn andererseits das Array bereits sortiert wurde oder wenn der Suchvorgang viele Male wiederholt wird, können die Berechnungskosten durch Verwendung der Dichotomie niedriger gehalten werden, selbst wenn die Sortierung ausgeführt wird.
Sie können die Dichotomie sowohl für eine Liste von Zeichen als auch für einen numerischen Wert verwenden. Dieses Mal werden wir jedoch als Beispiel mit einer Liste fortfahren, in der Ganzzahlen gespeichert sind.
Anstatt zu steuern, ob der Index des Suchergebnisses zurückgegeben wird, prüfen wir einfach, ob die Liste Werte enthält.
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:
"""
Führen Sie eine Dichotomie durch, um festzustellen, ob der gesuchte Wert in der Liste enthalten ist
Holen Sie sich den booleschen Wert.
Parameters
----------
sorted_list : list of int
Eine Liste mit sortierten Ganzzahlwerten.
search_value : int
Der zu durchsuchende Wert.
Returns
-------
value_exists : bool
Gibt an, ob der Wert in der Liste enthalten ist.
"""
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
Ich werde den Code der Reihe nach berühren.
Zunächst muss in der Dichotomie die Zielliste sortiert werden, damit die sortierte Funktion zum Sortieren der Liste verwendet wird (die Sortiermethode usw. ändert sich nicht).
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)
Als nächstes folgt die Verarbeitung der Dichotomiefunktion.
left_index: int = 0
right_index: int = len(sorted_list) - 1
Variablen für die Behandlung des Indexbereichs der Zielliste werden als left_index und right_index festgelegt. Der Index ganz links in der Liste ist left_index und der Index ganz rechts ist right_index. Diese Werte werden jedes Mal einseitig aktualisiert, wenn sie halbiert werden, bis die Schleife die Suche beendet.
while left_index <= right_index:
Der Teilungsvorgang wird wiederholt in einer while-Schleife ausgeführt. Diese Schleife wird wiederholt, solange sich der Index ganz links links vom Index ganz rechts befindet oder denselben Intex hat. Befindet es sich rechts neben dem Index am rechten Ende, ist der Bereich der Zielliste verschwunden (alle Ziele wurden durchsucht), sodass die Schleife beendet wird und beurteilt wird, dass das Ziel nicht gefunden wurde. ..
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
Middle_index in der Schleife speichert den Mittelwert im Zielarraybereich. Teilen Sie durch 2 durch // 2 und schneiden Sie den Bruch ab (//verhält sich zusätzlich zur Division wie ein Boden).
Es bezieht sich auch auf diesen Index sowie auf den zentralen Index und setzt den zentralen Wert auf die Variable (middle_value).
if search_value < middle_value:
right_index = middle_index - 1
continue
Wenn in der if-Anweisung der zu durchsuchende Wert kleiner als der Mittelwert ist, wird das Array nur in die linke Hälfte unterteilt, sodass der Index ganz rechts (right_index) links vom Mittelindex (middle_index --1") gesetzt wird. ).
if search_value > middle_value:
left_index = middle_index + 1
continue
Wenn der zu durchsuchende Wert jedoch größer als der Mittelwert ist, passen Sie den Wert des Index ganz links (left_index) so an, dass das Array nur die rechte Hälfte ist.
return True
Wenn der zu durchsuchende Wert weder kleiner noch größer als der Mittelwert ist, dh wenn er mit dem Mittelwert übereinstimmt, wird True zurückgegeben, da der zu durchsuchende Wert vorhanden ist.
return False
Ich werde es tatsächlich ausführen. Versuchen Sie zunächst unter der Bedingung, dass das Ziel in der Liste vorhanden ist.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=83)
print(value_exists)
True
True wird normal zurückgegeben. Geben Sie als Nächstes die Bedingungen an, unter denen das Suchziel nicht in der Liste enthalten ist.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=84)
print(value_exists)
False
Dies ist erwartungsgemäß auch falsch.
Recommended Posts