数値の検索(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