# -*- coding: utf-8 -*-
# 1から指定数までの数字が昇順に格納されたリストを用意する。
# 乱数にて探索値を生成し、上記リストを二分探索で探索して
# 探索値を見つけるまでに要した探索回数を記録する。
# 以上を指定回繰り返し、平均探索回数を算出する。
# 上記の平均探索回数と、理論値であるlog2(探索要素数)とを比較して示す。

import sys
import math
import random

# keyをリストyousoから探索し、見つかったら探索に要した回数を返す
def bin_search(key):
    low=MIN
    hi=MAX
    tansakusu = 0
    while True:
        tansakusu = tansakusu + 1
        print "探索回数= %s" % tansakusu
        index = (low + hi) / 2
        print "index= %s" % index
        if youso[index - 1] == key:
            return tansakusu
        elif youso[index -1] < key:
            print "真ん中の値 %s が探索値より小さいのでlowをindex+1の\
値に設定します" % youso[index -1]
            low = index + 1
        elif youso[index -1] > key:
            print "真ん中の値 %s が探索値より大きいのでhiをindex-1の\
値に設定します" % youso[index -1]
            hi = index -1
        if low > hi:
            return False        # 探索値が見つからなかった

#　メイン処理開始前の設定
MIN = 1
MAX = input("要素数をいくつにしますか？")
youso=[]
for i in range(MIN, MAX + 1):
    youso.append(i)
total=0
n = input("何回試行を行いますか？")
success = 0

#　メイン処理
for i in range(1, n + 1):
    print "*** 試行開始 %s 回目***" % i
    key = random.randint(MIN, MAX)
    print "探索値は %s" % key
    kekka = bin_search(key)
    if kekka == False:
        print "値 %sが見つかりませんでした。この値の探索をスキップします" \
                % i
        continue
    else:
        print "探索値を発見！"
        print "%s 回の探索で探索値 %s が見つかりました\n" % (kekka, key)
        total = total + kekka
        success = success + 1

print "*** 全試行終了 ***\n"
print "%s 個の要素の二分探索回数実測値平均は %s" % (MAX, (float(total) / \
float(success)) )
print "%s 個の要素の二分探索平均回数理論値は %s" % (MAX, math.log(MAX, 2))