リスト探索(線形探索・二分探索) – Python

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

線形探索

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

ALDS1_4_A:

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

[sourcecode language=”python” title=”” ]
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)
[/sourcecode]

二分探索

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

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

ALDS1_4_B:

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

[sourcecode language=”python” title=”” ]
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の(文字列)探索ライブラリ