Skip to content

Instantly share code, notes, and snippets.

@ankona
Created July 20, 2019 03:39
Show Gist options
  • Save ankona/668597a359a469c4d177176a8898385d to your computer and use it in GitHub Desktop.
Save ankona/668597a359a469c4d177176a8898385d to your computer and use it in GitHub Desktop.
non recursive binary search
def binsearch_nr(l, v):
m = len(l) // 2
mv = l[m]
start, end = 0, len(l) -1
while start <= end:
print(f'{start} of {end}. m {m}, mv {mv}')
if mv == v:
print(f"mv ({mv}) == v ({v})")
return True
else:
print(f"mv ({mv}) != v ({v})")
if v < mv: # the middle value is greater, so look at the left half.
print ('v < mv')
end = m - 1
m = (end - start) // 2 + start
mv = l[m]
else:
print ('v > mv')
start = m + 1
m = ((end - start) // 2) + start
mv = l[m]
print(f'start {start}, end {end}, m {m}, mv {mv}, l[m] {l[m]}')
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment