파이썬 알고리즘 207번 | [백준 10815, 1920번] 이분탐색 - 수찾기, 숫자카드

207. 이분탐색 - 수 찾기, 숫자 카드

1) 어떤 전략(알고리즘)으로 해결?

이분탐색 ! 매우 오랜만 인 것,,

2) 코딩 설명

<내 풀이>

1) 10815

import sys

n = int(sys.stdin.readline().rstrip())
lis = list(set(list(map(int, sys.stdin.readline().strip().split()))))
lis.sort()
m = int(sys.stdin.readline().rstrip())
mlis = list(map(int, sys.stdin.readline().strip().split()))

for i in range(len(mlis)) :
    l=0 ; r=len(lis)-1
    while l<=r:
        if lis[(l+r)//2] == mlis[i] : 
            print(1, end=" ");break
        elif lis[(l+r)//2] < mlis[i] :
            l = (l+r)//2+1
        elif lis[(l+r)//2] > mlis[i] :
            r = (l+r)//2-1

    else : print(0 ,end=" ")

2) 1920

import sys

n = int(sys.stdin.readline().rstrip())
lis = (list(map(int, sys.stdin.readline().strip().split())))
lis.sort()
m = int(sys.stdin.readline().rstrip())
mlis = list(map(int, sys.stdin.readline().strip().split()))

for i in range(m) :
    impossible=True
    l=0 ; r=n-1
    while l<=r:
        if lis[(l+r)//2] == mlis[i] : 
            impossible=False
            break
        elif lis[(l+r)//2] < mlis[i] :
            l = (l+r)//2+1
        elif lis[(l+r)//2] > mlis[i] :
            r = (l+r)//2-1

    if impossible: print(0)
    else : print(1)

<반성 점>

• 구현하는데 엄청 오래 걸렸다! ㅠㅠ 너무 오랜만에 해서 개념이 가물가물
• 크면 l을 mid+1, 작으면 r을 mid-1

<배운 점>