LoginSignup
13
11

More than 5 years have passed since last update.

pythonで二分探索

Last updated at Posted at 2012-12-26

初の二分探索を。
アルゴリズムの絵本の161PのC言語で書かれているものを自分なりにpythonに。
リストにない数字が入力された場合は機能しません。
リストの数字が昇順で並んでいること前提です。

nibun.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-

x = [1, 8, 14, 23, 44, 55, 67, 88, 103, 146]
print x
print "探したい数字を入力"
i = int(raw_input())

low = 0
high = len(x)
# t は中央番目の数
t = (low + high) / 2 

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかったということ
while (low<=high):
    if (i==x[t]):
        break
    elif (i > x[t]):
        low = t + 1
    elif (i < x[t]):
        high = t - 1
    t = (low + high) / 2

if (i==x[t]):
    print str(t + 1) + "番目にあります"
else:
    print "ありません"
13
11
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
13
11