1920.数字を探す

質問する
N個の整数A[1]、A[2]、...、およびA[N]が与えられた場合、Xという整数が存在するか否かを判定するプログラムを作成してください.
入力
第1行は自然数N(1≦N≦100000)を与える.次の行には、N個の整数A[1],A[2],...,A[N]が与えられる.次の行はM(1≦M≦100000)を与える.次の行はM個の数を与え、これらの数がAに存在するかどうかを見つければよい.すべての整数の範囲は-2です.³¹ 2以上³¹より小さい.
しゅつりょく
M行に答えを出力します.存在する場合は1を出力し、存在しない場合は0を出力します.예제 입력

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력

1
1
0
0
1

それをそのままリストに並べて線形探索で解くとタイムアウトが発生する.list型は演算を含む時間複雑度がO(n)であるため,演算を含む時間複雑度がO(1)のset資料型を用いて解くか,二分探索を用いて解く必要がある.
注意1-データ型別基本演算子の時間的複雑度1
注2-Pythonデータ型基本演算子の時間的複雑さ2

setデータ型で説明する

import sys

a = int(input())
n = set(sys.stdin.readline().split())
b = int(input())
m = sys.stdin.readline().split()
for i in m:
	print('1') if i in n else print('0')

二分探索を用いた解答

import sys

def binary_search(i, n, start, end):
    if start > end:
        return (0)
    mid = (start + end) // 2
    if i == n[mid]:
        return (1)
    elif i < n[mid]:
        return (binary_search(i, n, start, mid-1))
    else:
        return (binary_search(i, n, mid+1, end))
    
a = int(input())
n = sorted(map(int, sys.stdin.readline().split()))
b = int(input())
m = map(int, sys.stdin.readline().split())
start = 0
end = len(n) - 1
for i in m:
    print(binary_search(i, n, start, end))

上のゲームはバイナリ検索で解読され、関数が繰り返し呼び出され、sortプロセスも追加されたので、もっと時間がかかったようです.
他人が解読したコードを見た後、ディック・シャナリー資料型を利用して解読した.ディクシャナ変数を宣言し、自然数Nと1をキー値ペアとして追加し、Mの各数値の周りを回転させ、get関数でディクシャナに対応するキー値があるかどうかを確認します.ディクシャナ資料型のget関数の時間複雑度もset同様O(1)であるためタイムアウトは発生しない.
久しぶりにPythonで問題を解いた42ソウルではsi言語のみでプロジェクトを行い、js学習から本当に久しぶりにpythonでコードしました.kk map関数、sortとソートの違い、各資料型の演算はすべて再整理して、頭の中で言語を混同させないように気をつけますkk