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)
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
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
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