長野エンジニアライフ

東京から長野に移住したエンジニアのブログです。🦒🗻⛰

二分探索の実装

AIZU ONLINE JUDGEより、二分探索に関する問題(ALDS1_4_B)をpythonで解いていきます。 onlinejudge.u-aizu.ac.jp

問題自体は線形探索の時と同様ですが、入力値のn,qの最大値が増えているため線形探索で解答するとTLEとなります。

ちなみにsetクラスならこちらも、問題なくACでます。。

# setクラスを用いて実装
n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

temp = set(s) & set(t)
print(len(temp))

二分探索を用いて実装

二分探索の場合は、探索対象の配列が整列されていることを前提にしている探索手法となります。 探索対象値と配列の中央値を比較して、無駄な探索は省いていくよ〜って考えですね。

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

# 二分探索
def binarySearch(A: [int], key: int):
    left = 0
    right = len(A)
    mid = 0
    while left < right:
        mid = (left+right)//2
        if key == A[mid]:
            return 1
        if key > A[mid]:
            left = mid + 1
        elif key < A[mid]:
            right = mid;
    return 0

c = 0
# 前処理として整列させておく
s.sort()
for i in range(len(t)):
    if binarySearch(s, t[i]):
        c += 1
print(c)

同様な問題がでたら間違いなくsetクラスを使うのがおすすめですが、アルゴリズムの知識ということで、身につけておくのもいいと思います。