BOJ 1920. 수 찾기 (Python)

BOJ 1920. 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

풀이

이진 탐색(Binary Search) 으로 풀었다.
이진탐색의 원리는 이러하다.

 

1. 탐색하고자 하는 리스트를 오름차순으로 정리한다.
2. target < 중앙값 이면 target은 중앙값의 왼쪽에 있으므로 end(index)를 중앙값index - 1 로 설정하고 중앙값의 오른쪽은 버린다.
3. 중앙값 < target 이면 target은 중앙값의 오른쪽에 있으므로 start(index)를 중앙값index + 1 로 설정하고 중앙값의 왼쪽은 버린다.
4. 이를 반복한다.
5. 중앙값이 target과 일치한다면 found. 종료
6. 종료되지 못하고 end < start가 되면 탐색 실패. not found

소스코드

import sys
from typing import List
 
def binary_search(start: int, end: int, A: List, target: int, result: List):
    mid = (start + end) // 2
 
    # 종료 조건
    if end < start: # not found
        result.append(0)
        return
 
    if A[mid] == target: # found
        result.append(1)
        return
 
    if target < A[mid]:
        end = mid - 1
        return binary_search(start, end, A, target, result)
 
    if A[mid] < target:
        start = mid + 1
        return binary_search(start, end, A, target, result)
 
 
 
N = int(input())
list1 = list(map(int,sys.stdin.readline().rstrip().split()))
M = int(input())
list2 = list(map(int,sys.stdin.readline().rstrip().split()))
 
result = []
list1.sort()
 
for n in list2:
    binary_search(0, N-1, list1, n, result)
 
for n in result:
    print(n)