[백준] 1920번 파이썬 - 이분탐색

문제요약 ( 1920.수 찾기 )

주어진 리스트에 원하는 값이 있는지 찾아 출력한다..

 

풀이를 위한 부연 설명

• 정렬 알고리즘은 O(nlogn)의 시간 복잡도를 가진다.
• 이분탐색의 경우 O(nlogn)의 시간 복잡도를 가진다.
  • 이분 탐색은 정렬된 데이터에 대해 실행할 수 있으므로 미리 sort()해야한다.

 

코드 

import sys
input = sys.stdin.readline

num = int(input())
nums = list(map(int, input().split()))
nums.sort()
find = int(input())
finds = list(map(int, input().split()))

for target in finds:
    first = 0
    last = num - 1
    isFind = False
    while first <= last:
        mid = (first + last) // 2

        if target == nums[mid]:
            isFind = True
            break
        elif target < nums[mid]:
            last = mid - 1
        else:
            first = mid + 1

    if isFind:
        print(1)
    else:
        print(0)

 

 

기억할 점

• 이분 탐색을 수행해야한다는 사실만 알면 된다.