백준 1920 풀이 (수 찾기, 이분 탐색)

오늘 알고리즘 수업시간에 교수님이 설명해 주셨던 이분 탐색문제다. 문제는 원리는 크게 어렵지 않다.

1. start와 end의 중간인 mid를 정한다.

2. mid의 위치에 찾으려는 i 값과 비교한다.

3. 같으면 리턴한다. mid보다 i의 값이 크면 start=mid+1, mid보다 i가 작으면 end = mid-1을 해준다.

4. 찾을때까지 반복하다가 start < end를 만족하지 않으면 루프를 벗어난다.

 

이걸 코드로 짜면 아래와 같다. 단, 비교하려고 하는 리스트가 정렬되어 있는 경우에만 사용가능하다.

n  = int(input())
A = list(map(int, input().split()))
A.sort()
m = int(input())
B = list(map(int, input().split()))
def find(A,start, end,i):
    while start <= end :
        mid = (end+start)//2
        if A[mid] == i or A[end] == i:# mid가 맞으면
            return print(1)
        elif A[mid] < i: # 오른쪽에 있음
            start = mid+1
        else: # 왼쪽에 있음
            end = mid-1
    return print(0)
for i in B:
    find(A,0,n-1,i)