Skip to content

Instantly share code, notes, and snippets.

@lockdef

lockdef/binary_search.py

Created April 11, 2020 08:41
Show Gist options
  • Save lockdef/d84bb4a18cb9560787abbcd70eb66121 to your computer and use it in GitHub Desktop.
Save lockdef/d84bb4a18cb9560787abbcd70eb66121 to your computer and use it in GitHub Desktop.
Download ZIP
二分探索(めぐみ式)です
Raw
binary_search.py
# 参考 : https://qiita.com/drken/items/97e37dd6143e33a64c8c
a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]
def binary_search(key, list_):
def isOK(index, key):
if a[index] >= key:
return True
return False
ng = -1
ok = len(list_)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if isOK(mid, key):
ok = mid
else:
ng = mid
return ok
if __name__ == "__main__":
print(binary_search(51, a)) # Output : 3
print(binary_search(1, a)) # Output : 0
print(binary_search(52, a)) # Output : 6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment