AOJ 二分探索のPythonによる解答 3パターン

onlinejudge.u-aizu.ac.jp

この問題を3つの方法、二分探索を自分で実装する　、if T[i] in S　、pythonのライブラリbisectを使って解答してみます。

・1つ目　二分探索を自分で実装するやり方。

これは実際に二分探索を自分で関数として作るやり方です。二分探索については上のリンク先の一般回答という部分を参考にしました。

プログラムの説明としてbinary_searchで二分探索を実装して、あるリストlに値keyが含まれていたらTrue、含まれていないとFalseとしました。そして含まれていたらcntを+1していきます。

N=int(input())
S=list(map(int,input().split()))
Q=int(input())
T=list(map(int,input().split()))

def binary_search(n,l,key):  #n個あるリストlにkeyという値があるか
    left=0
    right=n
    while left<right:
        mid=(left+right)//2
        if l[mid]==key:
            return True
        elif key<l[mid]:
            right=mid
        else:
            left=mid+1
    return False
        
cnt=0
for i in range(Q):
  if binary_search(N,S,T[i]):
    cnt+=1
print(cnt)

・2つ目　if T[i] in Sを使う。
これはSというリストにT[i]が含まれたらcntを加算するやり方。注意としてPython3で提出するとTLEになるのでpypyで提出するとACになる。実装としては一番簡単にかける。

N=int(input())
S=list(map(int,input().split()))
Q=int(input())
T=list(map(int,input().split()))

cnt=0
for i in range(Q):
    if T[i] in S:
        cnt+=1
print(cnt)

・3つ目　pythonのライブラリのbisectを使う。
bisectは二分探索が簡単にできるライブラリです。これのbisect_leftとbisect_rightを使ってこれらの値が違うときにカウントしていく。(ある数字が含まれているとその数字の左に入れるか右に入れるかで値が違う)

import bisect
N=int(input())
S=list(map(int,input().split()))
Q=int(input())
T=list(map(int,input().split()))

cnt=0
for i in range(Q):
    bil=bisect.bisect_left(S,T[i])   #重複ががあれば左に
    bir=bisect.bisect_right(S,T[i])  #重複があれば右に
    #print(bil,bir)
    if bil!=bir:  #T[i]がSにあればbisect_leftとbisect_rightの値が異なる。
      cnt+=1
print(cnt)

最後に類題としてC - Gap Existence、公式の解答では2つ目のif in ：を使って解いていました。