[백준] 수 찾기 1920번 - Python

[백준] 수 찾기 1920번

나의 풀이

N = int(input())
nums = sorted(list(map(int, input().split())))
M = int(input())
targets = list(map(int, input().split()))

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return 1
        elif arr[mid] > target:
            end = mid - 1
        elif arr[mid] < target:
            start = mid + 1
    return 0

for i in targets:
    print(binary_search(nums, i, 0, N - 1))

• 이분 탐색(Binary Search):
  • 이분 탐색을 하기 전에 리스트는 오름차순 정렬이 되어 있어야 한다.
  • 해당 리스트의 중간 값을 기준으로 리스트의 시작과 끝을 조절하는 방식이다.
  • 중간 값과 같으면 해당 해당 인덱스를 반환한다.
  • 중간 값 보다 찾는 값이 더 크다면 시작점을 중간 + 1 로 옮기고 다시 탐색을 시작한다.
  • 중간 값 보다 찾는 값이 더 작다면 끝점을 중간 - 1 로 옮기고 다시 탐색을 시작한다.
  • 위 과정을 값을 찾을 때 까지 반복하다가 시작점이 끝점을 초과하게 되면 값이 없는 것으로 반복을 종료한다.
• 이분 탐색만 구현할 줄 알면 충분히 풀 수 있는 문제다.

느낀점

이것이 취업을 위한 코딩 테스트다. 에서 이분 탐색을 학습했기 때문에 쉽게 풀 수 있었다.