「アルゴリズムを、はじめよう」をPythonで書く第二弾。第一弾の線形探索法のアルゴリズムはこちら。
第5章:二分探索法のアルゴリズム
11,13,17,19,23,29,31という数字の中から17という数字をバイナリサーチのアルゴリズムで発見するという問題。
#!/usr/bin/env python
#-*- coding: utf-8 -*-
def main():
array = [11, 13, 17, 19, 23, 29, 31]
flag = -1
head = 0
tail = len(array) - 1
userNum = int(raw_input("Enter any number. : "))
while head <= tail:
center = (head + tail) / 2
if array[center] == userNum:
flag = center
break
elif array[center] < userNum:
head = center + 1
else:
tail = center -1
center = (head + tail) / 2
if flag == -1:
print "The number doesn't exitsts."
else:
print "The number is in the array[%d]." % flag
if __name__ == '__main__':
main()
ユーザーが任意の数を入力できるようにしています。
間違いや改善方法など、何でもご意見いただければ嬉しいです。