1920번 : 수 찾기

문제보기

파이썬

def binary_search(nums, target):
    # 이진 탐색으로 구현
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return 1
        elif nums[mid] > target:
                right = mid - 1
        else:
            left = mid + 1
    return 0


n = int(input())
nums = list(map(int, input().split()))

m = int(input())
mums = list(map(int, input().split()))

nums.sort()
for i in mums:
    target = i
    if binary_search(nums, target):
        print(1)
    else:
        print(0)

풀이

• 처음에는 그냥 for문으로 했지만 시간초과 발생
• 반복문안에서 빠르게 값을 찾아갈수 있는 이진탐색 사용