백준 1920번 파이썬 _ 수 찾기(이진탐색)

www.acmicpc.net/problem/1920

1920번: 수 찾기

문제유형 : 이진탐색

문제풀이 :

• n과m의 범위가 10만까지이므로 완전탐색을 진행하면 n*m이 되므로 시간초과가 남을 예상하고 탐색에서 logN의 시간을 갖는 이분탐색을 떠올려야한다.

이진탐색 정리! 

• 이진탐색은 정렬된 배열을 대상으로 한다.
• 이진탐색 함수의 매개변수에는 배열, 타겟(찾고자하는 값), 시작인덱스, 끝인덱스 를 필요로한다.
• 찾고자하는 값이 없을때에 대하여 start > end 일경우 None을 반환하는 부분이 꼭 필요하다.
• 이후로는 매개변수로 들어온 값을 이용하여 중간값을 구하고, 조건에 따라 재귀함수호출을 리턴한다.

정답코드:

import sys
input = sys.stdin.readline

def binary_search(array, target, start, end): #타겟값, 시작인덱스, 끝인덱스
    if start > end :
        print(0)
        return None
    mid = (start+end) // 2
    if array[mid] == target:
        print(1)
        return mid
    elif array[mid] < target: #중간값이 타겟보다 작으면 범위를 더 오른쪽으로
        return binary_search(array, target, mid+1, end)
    else:
        return binary_search(array, target, start, mid-1)

n = int(input())
a = sorted(list(map(int, input().split())))

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

for i in num_list:
    binary_search(a, i, 0, len(a)-1)