수찾기 - 이진 탐색 (파이썬)

사이트 링크 : https://www.acmicpc.net/problem/1920

 

문제는 아래와 같습니다.

문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

문제 해결 포인트 

• 해당문제는 정형화된 이진 탐색 문제입니다. 
• 입력받은 수가 해당 리스트에 값이 있는지만 확인하면되는데 탐색 버무이가 너무 넒어 이진 탐색으로 시간 복잡도를 줄여야하는 문제 었습니다. 
• start,end를 리스트에 최소 최대로 두고 이진탐색을 하면 문제를 풀어나갔습니다. 

정답코드 

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

n_list.sort()


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        elif array[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1
    return None

for m_num in m_list:
    if binary_search(n_list, m_num, 0, n-1) == None:
        print(0)
    else:
        print(1)

 

 

이코테 깃허브에서 거의 동일하게 코드를 작성하였는데 통과가 되었네요 ~~ ^^