d732: 二分搜尋法

http://zerojudge.tw/ShowProblem?problemid=d732

A串用index方法搜尋最多2*len(B)次 => TLE

• 當每個b都是A[-1]

• input()
• A = input().split()
• B = input().split()
• for b in B:
•   if b in A:
•     print(A.index(b)+1)
•   else:
•     print(0)

A串用index方法搜尋len(B)次 => TLE

• input()
• A = input().split()
• B = input().split()
• for b in B:
•   try:
•     print(A.index(b)+1)
•   except:
•     print(0)

AB兩遞增串掃描比對一次 => AC

• import operator
• input()
• A=[int(a) for a in input().split()]
• B=[int(b) for b in input().split()]
• B=enumerate(B) # https://docs.python.org/3/library/functions.html#enumerate
• sortedB=sorted(B, key=operator.itemgetter(1))
• sortedBplus=[]
• i=0
• for b in sortedB:
•   b=list(b)
•   while b[1]>A[i]:
•     i+=1
•   if b[1]==A[i]:
•     b.append(i+1)
•   else:
•     b.append(0)
•   sortedBplus.append(b)
• unsortedB=sorted(sortedBplus, key=operator.itemgetter(0))
• for b in unsortedB:
•   print(b[2])

• 測資的len(A)和len(B)一定很大，len(A)乘len(B)就更大，一一搜尋就會TLE
• 必須降低算法的時間複雜度
• 沒用到二分搜尋法就AC，對不起零法官 :raising_hand: 
• 搶到這題的Python頭香 :sunglasses: