数値の検索(1920)
Binary Search
質問する
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に存在するかどうかを見つければよい.すべての整数の範囲は、231未満の-231以上です.
しゅつりょく
M行に答えを出力します.存在する場合は1を出力し、存在しない場合は0を出力します.
import sys
input = sys.stdin.readline
n = int(input())
N = sorted(list(map(int, input().split())))
m = int(input())
M = list(map(int, input().split()))
def binarySearch(target, N, start, end):
if start > end:
return 0
m = (start + end) // 2
if target == N[m]:
return 1
elif target < N[m]:
return binarySearch(target, N, start, m - 1)
else:
return binarySearch(target, N, m + 1, end)
for target in M:
start = 0
end = len(N) - 1
print(binarySearch(target, N, start, end))
参照)https://chancoding.tistory.com/44
Reference
この問題について(数値の検索(1920)), 我々は、より多くの情報をここで見つけました https://velog.io/@skkfea07/백준-수-찾기1920テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol