3, 7, 12, 15, 18, 23, 25, 26, 30
Angenommen, Sie möchten 25 aus einer Reihe von Spalten finden, die in aufsteigender Reihenfolge angeordnet sind, z.
Die lineare Suche ist eine Methode, um von Anfang an in der unten gezeigten Reihenfolge zu suchen.
a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
HowManyLoops = 0
for i in a:
if i == 25:
break
HowManyLoops += 1
print('a[{}]Es ist in.'.format(HowManyLoops))
a[6]Es ist in.
Als nächstes wollen wir sehen, wie man eine Dichotomie macht. Wie der Name schon sagt, ist die Dichotomie eine Methode, um die Anzahl der zu untersuchenden Elemente während der Dichotomisierung zu verringern. Die Methode ist wie folgt.
In diesem Beispiel wurden nur zwei Suchvorgänge durchgeführt. Lassen Sie es uns tatsächlich im Code sehen.
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[{}]Es ist in.'.format(pc))
break
if pr < pl:
print('Die Suche ist fehlgeschlagen.')
break
print('Die Schleife ist{}Es gab Zeiten.'.format(HowManyLoops))
a[6]Es ist in.
Es gab zwei Schleifen.
Auf diese Weise konnten wir in zwei Schleifen suchen. Ich werde die Quelle ein wenig erklären. Die Punkte sind pl, das den Index ganz links des Arrays darstellt, das Sie betrachten, pr, das den Index ganz rechts darstellt, und pc, das die Mitte darstellt. Wenn sich das Element, das Sie suchen möchten, auf der rechten Seite von pc befindet (pc <Element, das Sie suchen möchten), setzen Sie pc + 1 als pl, und wenn sich das Element, das Sie suchen möchten, auf der linken Seite von pc befindet (pc> Element, das Sie suchen möchten), setzen Sie pc-1 als pr. Betrachten Sie ein neues Subarray. Auf diese Weise wird die Anzahl der Elemente in dem interessierenden Unterarray in zwei Teile geteilt. Und wenn Sie feststellen, dass der PC das Element ist, nach dem Sie suchen möchten, weil Sie ihn in zwei Teile geteilt haben, ist die Suche erfolgreich.
Bisher haben wir den Fall einer erfolgreichen Suche gesehen, aber was ist mit dem Fall einer fehlgeschlagenen Suche? In Bezug auf die Quelle
if pr < pl:
print('Die Suche ist fehlgeschlagen.')
break
Es ist der Teil von. Übrigens ist dieser Teil ein Prozess, bei dem die Suche fehlschlägt, wenn der Index ganz links des Teilarrays den Index ganz rechts überschreitet. Wird dies passieren? Um dies zu sehen, das obige Array
a = [3, 7, 12, 15, 18, 23, 25, 26, 30]
# 0 1 2 3 4 5 6 7 8
Schauen wir uns die Schritte an, um nach der Zahl von bis 27 zu suchen. Natürlich gibt es in diesem Array keine 27, daher schlägt die Suche fehl.
--Vergleichen Sie die Elemente 18 und 27 von Index 4 in der Mitte (pl = 0, pr = 8, pc = 4).
Unabhängig davon, ob die Anzahl der Elemente im ursprünglichen Array gerade oder ungerade ist, ist die Anzahl der Elemente im interessierenden Unterarray nach der ersten Suche eine gerade Zahl, sodass sich der Suchfluss im Grunde nicht ändert. Im Suchfehlermuster ist pl = pr = pc beim Eintritt in die letzte Schleife, dh die Anzahl der Elemente im Subarray beträgt 1. Wenn daher das Element, das Sie suchen möchten, größer als dieses letzte Element ist, pl = pc + 1, und wenn es kleiner ist, pr = pc-1, wird pl pr überschreiten. Es bricht zu diesem Zeitpunkt.
Recommended Posts