• このエントリーをはてなブックマークに追加

こんにちは。今日は、AOJ の問題に取り組むことで、探索の勉強をしてみました!

スポンサードリンク

線形探索

リストや配列に入ったデータに対する検索を行うにあたって、 
先頭から順に比較を行い、それが見つかれば終了する.

ALDS1_4_A:

サンプル問題(AOJ): http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def linearSearch(A, n, key):
    i = 0
    A.append(key) # 番兵
    while A[i] != key:
        i += 1
    A.pop()
    return i != n

count = 0

for i in range(q):
    if linearSearch(S, n, T[i]):
        count += 1

print(count)

二分探索

ソート済み配列に対する探索アルゴリズムの一つ

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、
中央の値を見て、検索したい値との大小関係を用いて、
検索したい値が中央の値の右にあるか、左にあるかを判断して、
片側には存在しないことを確かめながら検索していく

ALDS1_4_B:

サンプル問題(AOJ): http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

def binary_search(A, key):
left = 0
right = n
while left < right: mid = int((left + right)/2) if A[mid] == key: return True elif key < A[mid]: right = mid else: left = mid + 1 return False cnt = 0 for i in T: if binary_search(S, i): cnt += 1 print(cnt) [/sourcecode]

Pythonの(文字列)探索ライブラリ