I recently wrote an article about recursive functions. I didn't intend to use it, but it was for studying, but I needed an efficient search. It was saved because I should have just improved the published 2-minute search. Since it's a big deal, I'll publish that the improved function may be useful. (Although I'm actually using Javascript instead of Python, and it has a different implementation)
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) #Truncate
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) #Round up
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