[백준] 1920번 : 수 찾기 (파이썬)

문제

나의 답안

def find(i,s,e):
    if s>e:
        return 0
    k=(s+e)//2 #가운데 인덱스
    if i==a[k]: #두 값이 같다면 1반환
        return 1
    elif i>a[k]:#i가 더 크다면 a[k]우측에 존재
        return find(i,k+1,e)
    else:#i가 더 작다면 a[k]좌측에 존재
        return find(i,s,k-1)
n=int(input())
a=list(map(int,input().split()))

n2=int(input())
a2=list(map(int,input().split()))

a.sort()
#a2.sort()

for i in a2:
    s=0 #시작인덱스
    e=n-1# 끝인덱스
    print(find(i,s,e))

이진 탐색 문제이다. 재귀로 풀어주었다.
1. 이진탐색 함수를 정의해준다.
함수의 인자는 검사할 배열(두번째)의 값, 시작 인덱스, 끝 인덱스 값을 받는다.
우선 가운데 인덱스를 구해준다. 이를 k로 한다.
만약 첫번째 배열의 값과 두번째 배열의 값이 같다면 1을 반환해준다.
2. 만약 두번째 배열의 값이 더 크다면 s값을 k+1로 변경하고 함수를 다시 호출해준다.
3. 마지막으로 두번째 배열의 값이 더 작다면 e값을 k-1로 변경하고 함수를 다시 호출한다.

---

4. 이진탐색을 사용하기 위해 첫번째 배열을 오름차순으로 정렬해준다.
5. 반복문을 통해 두번째 배열(a2)을 첫값부터 순차적으로 접근하고, find함수를 호출한다.