[백준][1920] 수 찾기 (Python)

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

1920번: 수 찾기

C++로만 알고리즘을 공부하다가 이번 방학엔 파이썬 공부도 할 겸 알고리즘 기초 단계부터 시작할 계획입니다. C++ 위주로 알고리즘 공부를 했다보니 입력받는 거랑 타입 같은 게 많이 헷갈리네요. input() 함수는 str 타입으로 입력되기 때문에 꼭 int(input())으로 받아줘야 에러가 나지 않아요! 이것때문에 TypeError: unsupported operand type(s) for -: 'str' and 'int' <-- 이런 오류가 계속 나더라구요 이걸 고쳐주니 바로 풀렸습니다

수 찾기 성공

문제

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

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

이분탐색은 전체 배열 (정렬되어 있어야 합니다) 을 반으로 나누어 가운데를 기준으로 왼쪽에 속하면 왼쪽 배열만 다시 탐색하고 오른쪽에 속하면 오른쪽 배열만 다시 탐색해주는 방법입니다. 재귀함수를 이용하면 간편하게 탐색할 수 있습니다. 또 계속해서 탐색할 인덱스를 갱신해주는데 low가 high보다 크게되면 찾는 수가 배열에 없다는 뜻이기 때문에 return해주면 됩니다. 

N = int(input())
 
arr1 = list(map(int, input().split()))
arr1.sort()
 
M = int(input())
 
arr2 = list(map(int, input().split()))
 
 
def solution(i, arr, low, high):
    mid = (low + high) // 2
    if i == arr[mid]:
        print(1)
        return
    if low >= high:
        print(0)
        return
    
    if i < arr[mid]:
        solution(i, arr, low, mid - 1)
    else:
        solution(i, arr, mid + 1, high)
 
for k in arr2:
    solution(k, arr1, 0, N-1)