Einführung in die binäre Suche und detaillierte Beispiele

Einführung in die binäre Suche

Die binäre Suche wird auch als halbe Suche bezeichnet. Die Grundidee der binären Suche besteht darin, davon auszugehen, dass die Elemente im Wörterbuch von klein bis geordnet in einem Array gespeichert sind groß. ,

Vergleichen Sie zuerst den angegebenen Wertschlüssel mit dem Schlüssel des Elements in der Mitte des Wörterbuchs. Wenn sie gleich sind, ist der Abruf erfolgreich.

Andernfalls ist der Schlüssel gleich Wenn der Schlüssel groß ist, wird er in der ersten Hälfte des Wörterbuchs fortgesetzt.

Auf diese Weise wird das Abrufintervall nach einem Vergleich um die Hälfte reduziert und dies so lange, bis der Abruf erfolgreich ist oder fehlschlägt.

Nehmen Sie eines der beiden mittleren Elemente einer geraden Zahl als mittleres Element

Binärer Abruf ist eine effizientere Abrufmethode, bei der das Wörterbuch nach Schlüssel in der Sequenztabelle sortiert werden muss .

Codebeispiel:

Ausführen:

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

Bemerkungen:

python@pythontab:~$ python BinarySearch.py 123456789 4
3

1.'__': Da die Klassenmitglieder von Python öffentlich sind, öffentlicher Zugriff öffentlich, es fehlen private Eigenschaften wie bei herkömmlichen objektorientierten Sprachen.

Also habe ich einfach __ verwendet, um private Attribute zu simulieren. Diese __-Attribute werden häufig intern verwendet und müssen normalerweise nicht überschrieben werden. Auch das Lesen ist nicht nötig.

Der Zweck des Hinzufügens von zwei Unterstrichen besteht darin, keinen Konflikt mit allgemeinen öffentlichen Attributen mit demselben Namen zu verursachen und zweitens zu verhindern, dass Benutzer des Objekts (Nicht-Entwickler) es nach Belieben verwenden.

2.__name__ == „__main__“ bedeutet, dass das Programmskript direkt ausgeführt wird.

Wenn es nicht gleich ist, bedeutet dies, dass das Skript von anderen Programmen importiert wird ist auf den Modulnamen

gesetzt

Das obige ist der detaillierte Inhalt vonEinführung in die binäre Suche und detaillierte Beispiele. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!