今日は二分探索の練習問題。
二分探索とは、予めソートされている列に対して、中央値と探索対象の値の大小を比べることで探索範囲を半分づつに絞っていく方法。
計算量はO(logn)で、O(n)の線形探索に比べてだいぶはやい。
問題はこれ。
んで解答。
n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
c = 0
for i in t:
left = 0
right = n
mid = lambda x,y:(x + y)/2
while left < right:
if s[int(mid(left,right))] == i:
c += 1
break
elif s[int(mid(left,right))] > i:
right = int(mid(left,right))
else:
left = int(mid(left,right)) + 1
print(c)
そろそろpython用のアルゴリズム本なり、最適化本なり買わないとどこで差がついてるのイマイチわからん。
これでだいたい1.3secとかで１位は0.03sec。
まあ上位の人達はset型の関数とか使ってるんでぶっちゃけ二分探索はしていないくせこである。
おしまい。