[python] 백준 > 이분 탐색 > 수 찾기(1920)

[문제]

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

[나의 풀이]

import sys
input = sys.stdin.readline

N = int(input())
AN = list(map(int, input().split()))
M = int(input())
MN = list(map(int, input().split()))

AN = sorted(AN)

for val in MN:
    start = 0
    answer = 0
    end = len(AN)-1
    while start <= end:
        mid = (start+end) // 2
        if val < AN[mid]:
            end = mid - 1
        elif val > AN[mid]:
            start = mid + 1
        if val == AN[mid]:
            answer = 1
            break
    print(answer)

 

• 정렬을 하여 이분탐색을 통해 찾고자 하는 값이 있는지 확인한다.
• 찾고자 하는 값 보다 현재 찾은 값이 더 크다면 end를 줄여준다.
• 찾고자 하는 값 보다 현재 찾은 값이 더 작다면 start를 늘려준다.
• 값이 있다면 1을 없다면 0을 프린트해준다.

[다른 사람의 풀이]

from sys import stdin, stdout
n = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())

def binary(l, N, start, end):
    if start > end:
        return 0
    m = (start+end)//2
    if l == N[m]:
        return 1
    elif l < N[m]:
        return binary(l, N, start, m-1)
    else:
        return binary(l, N, m+1, end)

for l in M:
    start = 0
    end = len(N)-1
    print(binary(l,N,start,end))

 

from sys import stdin, stdout
n = stdin.readline()
N = set(stdin.readline().split())
m = stdin.readline()
M = stdin.readline().split()

for l in M:
    stdout.write('1\n') if l in N else stdout.write('0\n')