7/22(水)　アルゴリズムとデータ構造　on

13:00～13：10
・今日のテーマ
・処理速度の差を見よう(線形探索と二分探索)

～14：30
・線形探索と二分探索のコードを書き、処理速度の差を見る
↓以下そのコード↓

import random
import time

#探索対象の数字
key=-1

#探索するリスト
listnum=[]

#線形探索
def l_search(a,key):
 #結果を入れる　先頭だったら０
 index=-1
 #ループの回数
 i=0
 
 while True:
if a[i]==key:
     index=i
     break
if i==len(a)-1:
     break
i=i+1
return index

#二分探索
def b_search(a,key):
pl=0
 pr=len(a) -1
while True:
   pc=(pl + pr) // 2
   if a[pc] == key :
      return pc
   elif a[pc] < key :
     pl=pc + 1
   else:
     pr=pc -1
   if pl >pr :
     break
 return -1
 
 
#リスト要素数とループ回数
size=10000
loop=100
#リスト生成
for i in range(1,size):
 listnum.append(i)
key = random.randint(1,size)
print(key)
print(l_search(listnum,key))
print(b_search(listnum,key))


#線形探索実行
start = time.time()
for i in range(1,loop):
 key = random.randint(1,size)
 l_search(listnum,key)
elapsed_time = time.time() -start
print("time:{0}" . format(elapsed_time) + "[sec]")


#二分探索実行
start = time.time()
for i in range(1,loop):
 key = random.randint(1,size)
 ｂ_search(listnum,key)
elapsed_time = time.time() -start
print("time:{0}" . format(elapsed_time) + "[sec]")

※コピペしてるんでコードのインデントが違ってる箇所あると思いますが、自分で修正お願いします。(気が向いたら直してみますが)

※課題なし
※授業中に殴り書きしているので間違えあったらすいません。
※何かありました連絡ください