백준 1920번 수 찾기

이분 탐색을 이용해서 숫자를 찾는다

 

이진 탐색

이진 탐색은 정렬이된 리스트나 배열에서 사용이 가능하다 그래서 먼저 리스트를 정렬하고 중간지점을 찾아 중간지점의 수와 탐색하는 숫자를 비교하고 크면 오른쪽범위의 절반을 찾아 다시 비교한다

이런식으로 반복하면 탐색하는 횟수를 순차탐색에 비해 반을 절약할 수 있다

 

문제 해결

먼저 N,M과 찾을 리스트 A와 목표값이 저장된 리스트 B를 입력 받는다

그 다음 B의 값을 for문으로 찾아낸다

import sys

A = []
B = []
N = int(sys.stdin.readline().strip())

#리스트
A = list(map(int,sys.stdin.readline().strip().split()))

M = int(sys.stdin.readline().strip())

#찾을 대상
B = list(map(int,sys.stdin.readline().strip().split()))

A.sort() #이진 탐색을 위한 정렬

for target in B: #이진탐색 과정
    start = 0
    end = len(A)-1
    a=0

    while start <= end:
        mid = (start + end)//2

        if A[mid] == target:
            print(1)
            a = 1
            break

        elif A[mid] < target:
            start = mid+1

        elif A[mid] > target:
            end = mid-1

    if a == 0: #겹치는 값이 없는 경우
        print(0)