[백준 1920번] 수 찾기(이진 탐색) python

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

<조건>
1. 정수 n 입력
2. n개의 리스트 입력
3. 정수 m 입력
4. m개의 리스트 입력
5. m의 요소가 n에 포함되어 있으면 1, 아니면 0 출력

def binarySearch(target):
    left=0; right=n-1

    while left<=right:
        mid=(left+right)//2
        if n_list[mid]==target:
            return True
        elif n_list[mid]>target:
            right=mid-1
        elif n_list[mid]<target:
            left=mid+1
            
    return False

n=int(input())
n_list=list(map(int, input().split()))
n_list.sort()
m=int(input())
m_list=list(map(int, input().split()))

for target in m_list:
    if binarySearch(target):
        print(1)
    else:
        print(0)

 

 

 

---

코드짜는데 꽤 오래 걸렸다. 

1.  처음에 이런 식으로 풀었는데 (당연하게도) 실패가 떴다. 그래서 원래 문제 의도대로 이진 탐색으로 풀었는데, 

n=int(input())
n_list=[list(map(int,input().split()))]

m=int(input())
m_list=list(map(int,input().split()))

for i in m_list:
    if i in n_list:
        print(1)
    else:
        print(0)

 

2.  이진 탐색 개념만 알고 코드가 생각이 안 났더니 이런 코드가 나왔다ㅋㅋㅋㅋ

def search(n_list, m, index):
    if index>len(n_list)-1 or index<0:
        return 0

    if n_list[index]==m:
        return 1
    elif n_list[index]>m: #왼쪽
        return search(n_list, m, index-1)
    else:
        return search(n_list, m, index+1)

n=int(input())
n_list=list(map(int,input().split()))
n_list.sort()
m=int(input())
m_list=list(map(int,input().split()))

for i in m_list:
    result=search(n_list, i, len(n_list)//2)
    print(result)

 

 

3.  이때까지만 해도 뭐가 잘못된 줄 몰라서 재귀 호출 에런가?ㅎㅎㅎ 이러고 에러 검색하고 수정했는데고 재귀호출 에러가 나더라. 파이썬 재귀호출 최대 깊이가 기본 1000이어서 10**6으로 바꿔줬는데. 응 어림도 없지 ㅅㅂ..

import sys
sys.setrecursionlimit(10**6)  #재귀호출 깊이를 10**6까지

def search(n_list, m, index):
    if index>len(n_list)-1 or index<0:
        return 0

    if n_list[index]==m:
        return 1
    elif n_list[index]>m: #왼쪽
        return search(n_list, m, index-1)
    else:
        return search(n_list, m, index+1)

n=int(input())
n_list=list(map(int,input().split()))
n_list.sort()
m=int(input())
m_list=list(map(int,input().split()))

for i in m_list:
    result=search(n_list, i, len(n_list)//2)
    print(result)

 

4.  재귀호출이 문제야? 그럼 반복문으로 바꿀께!

n=int(input())
n_list=list(map(int,input().split()))
n_list.sort()
m=int(input())
m_list=list(map(int,input().split()))

for i in m_list:
    index=n//2
    result=0

    while index<=len(n_list)-1 and index>=0:
        if n_list[index]==i:
            result=1
            break
        elif n_list[index]>i: #왼쪽
            index-=1
        else:
            index+=1

    print(result)

 

"응 아니야~"

 

5. 겨우겨우 이진탐색 알고리즘 찾아봐서 성공...

def binarySearch(target):
    left=0; right=n-1

    while left<=right:
        mid=(left+right)//2
        if n_list[mid]==target:
            return True
        elif n_list[mid]>target:
            right=mid-1
        elif n_list[mid]<target:
            left=mid+1
            
    return False

n=int(input())
n_list=list(map(int, input().split()))
n_list.sort()
m=int(input())
m_list=list(map(int, input().split()))

for target in m_list:
    if binarySearch(target):
        print(1)
    else:
        print(0)