[Pyson/Python/Baekjunアルゴリズム]1920.数値の検索


最初の試み

import sys

N = int(input())
A = list(map(int,sys.stdin.readline().split()))
M = int(input())
tmp = list(map(int,sys.stdin.readline().split()))
result=[0]*M

for i in range(M):
    if tmp[i] in A:
        result[i]=1
for i in result:
    print(i)
Python inで以下のように説明した.
でもPython 3を使うとタイムアウトしてPyPy 3を使うのが正しい
そこでネットで検索してみると、バイナリで検索した接着剤であることがわかりました.

バイナリ・ナビゲーションの使用

import sys
def binary_sort(x,a):
    start=0
    end=len(a)-1
    while (start <= end):
        mid = (start+end)//2
        if x == a[mid]:
            return 1
        elif x > a[mid]:
            start = mid+1
        else:
            end = mid-1
    return 0

N = int(input())
A = list(map(int,sys.stdin.readline().split()))
A.sort()

M = int(input())
X = list(map(int,sys.stdin.readline().split()))
for x in range(M):
    print(binary_sort(X[x],A))