[GO] Python 2-Minuten-Suche und ihre Ableitungen

Einführung

Ich habe kürzlich einen Artikel über rekursive Funktionen geschrieben. Ich hatte nicht vor, es zu benutzen, aber es war zum Lernen da, aber ich brauchte eine effiziente Suche. Es wurde gespeichert, weil ich gerade die veröffentlichte 2-Minuten-Suche hätte verbessern sollen. Da es eine große Sache ist, werde ich veröffentlichen, dass die verbesserte Funktion nützlich sein kann. (Obwohl ich tatsächlich Javascript anstelle von Python verwende und es eine andere Implementierung hat)

Finden Sie n

python


def binarySearchL(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = int(l + (r - l) / 2)
    middleValue = lt[middleIndex]
    if middleValue > n:
      l, r = l, middleIndex - 1
    elif middleValue < n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

Finden Sie die kleinste größer als n

python


def binarySearchGt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.floor(l + (r - l) / 2)  #Kürzen
    middleValue = lt[middleIndex]
    if middleValue > n and r - l > 1:
      l, r = l, middleIndex
    elif middleValue <= n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

Finden Sie die größte weniger als n

python


def binarySearchLt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.ceil(l + (r - l) / 2)  #Zusammenfassen
    middleValue = lt[middleIndex]
    if middleValue >= n:
      l, r = l, middleIndex - 1
    elif middleValue < n and r - l > 1:
      l, r = middleIndex, r
    else:
      return middleIndex
  return -1

Recommended Posts

Python 2-Minuten-Suche und ihre Ableitungen
[Python] Suche nach Tiefenpriorität und Suche nach Breitenpriorität
Suchen und spielen Sie YouTube-Videos mit Python
Suchen und laden Sie YouTube-Videos automatisch mit Python herunter
Kausales Denken und kausale Suche von Python (für Anfänger)
[Python] Komprimieren und dekomprimieren
Python- und Numpy-Tipps
[Python] Pip und Wheel
Sequentielle Suche mit Python
Python-Übung 1-Breiten-Prioritätssuche
Python Iterator und Generator
[Python] Suche (itertools) ABC167C
Dichotomie mit Python
Python-Pakete und -Module
Vue-Cli- und Python-Integration
Memo zur Bisektionssuche (python2.7)
[Python] Bisection-Suche ABC155D
Python-Eingabe und Ausgabe
Python und Ruby teilen sich
Crawlen mit Python und Twitter API 1-Einfache Suchfunktion
Es ist nicht einfach, Python zu schreiben, es ist einfach, numpy und scipy zu schreiben
Finden Sie die Hermite-Matrix und ihre eindeutigen Werte in Python
Python Bit vollständige Suche
Lineare Suche in Python
Dichotomie mit Python
Suchen Sie Twitter mit Python
Suchen Sie rekursiv nach Dateien und Verzeichnissen in Python und geben Sie sie aus
Binäre Suche in Python
Python asyncio und ContextVar
Implementieren Sie die Suche nach Tiefenpriorität (DFS) und die Suche nach Breitenpriorität (BFS) in Python
Anwendung zum Anzeigen und Durchsuchen lokaler Memos (Tagebuch) in Python
Programmieren mit Python und Tkinter
[Python] BFS (Suche nach Breitenpriorität) ABC168D
Python: Klassen- und Instanzvariablen
Python 2-Serie und 3-Serie (Anaconda Edition)
Python und Hardware-Verwenden von RS232C mit Python-
Python-Einzug und String-Format
Python Real Number Division (/) und Integer Division (//)
Installieren Sie Python und Flask (Windows 10)
Informationen zu Python-Objekten und -Klassen
Informationen zu Python-Variablen und -Objekten
Apache mod_auth_tkt und Python AuthTkt
Å (Ongustorome) und NFC @ Python
Lernen Sie Python-Pakete und -Module kennen
# 2 [python3] Trennung und Kommentar aus
Flache Python-Kopie und tiefe Kopie
Python und Ruby Slice Memo
Python-Installation und grundlegende Grammatik
Suche nach Breitenpriorität / bidirektionale Suche (Python Edition)
Ich habe Java und Python verglichen!
Prophezeiungstheorie und ihre Simulation (2)
Homebrew Python - Youtube Suchprogramm
[Python] DFS (Tiefenprioritätssuche) ATC001A
Binäre Suche in Python / C ++
Algorithmus in Python (Dichotomie)
Über Python, len () und randint ()
Informationen zu Python-Datums- und Zeitzone
Vollbit-Suche mit Python