이진 탐색

이진탐색 (Binary Search)

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

 

 

참고) 리스트 정렬 시키기

import random

data_list = random.sample(range(100), 10)
// 원본 리스트가 바뀜
data_list.sort()

 

 

예제 코드

# 백준 1920. 수 찾기
#
# 링크: https://www.acmicpc.net/problem/1920

n = int(input())
n_list = list(map(int, input().split()))
n_list.sort()
m = int(input())
m_list = map(int, input().split())


def binary_search(num, start, end):
    if start > end:
        return False

    mid = (start+end) // 2

    if n_list[mid] > num:
        return binary_search(num, start, mid-1)
    elif n_list[mid] < num:
        return binary_search(num, mid+1, end)
    else:
        return True


for i in m_list:
    if binary_search(i, 0, n-1):
        print(1)
    else:
        print(0)