[Python] 백준 1920 수 찾기

N=int(input())

first=list(map(int,input().split()))

M=int(input())

second=list(map(int,input().split()))
for i in range(M):
  check=1
  for j in range(len(first)):
    if(second[i]==first[j]):
  
      print("1")
      check=0
      break
  if(check==1):
    print("0")

이중반복문을 사용하여 일일이 비교를 했더니 시간초과가 발생하였다. 

 

문제해결을 위해 이진 탐색 알고리즘(Binary Search)을 사용했다. 이진 탐색을 적용 할 수 있는 전제 조건은 오름차순으로 정렬된 리스트이다.  앞에서 했던 코드처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아닌, 

탐색 범위를 절반씩 줄여가면서 값을 찾아가는 방식이다. 

 

예를 들어 1, 3, 5, 7, 9, 11,13 이라는 리스트에서 11이라는 값을 찾고자 한다면, 리스트에 중간에 있는 7이라는 값과 11을 비교 한다. 11은 7보다 크므로 7의 왼쪽에 위치하는 값들은 탐색 할 필요가 없게된다(정렬된 데이터이므로)

7의 오른쪽 부분 9,11,13 값만 고려하여 다시, 중간값인 11을 찾고 11과 11을 비교하면 값이 일치하므로 탐색을 종료한다.  

def binary(first,value,start,end):
  if(start>end): ##종료 조건
    return 0

  mid=int((start+end)/2)

  if(value==first[mid]): ## 값을 찾음.
    return 1
  
  elif(first[mid]<value): # 값이 크다면 중간+1 부분만 고려
    return binary(first,value,mid+1,end)
  
  elif(first[mid]>value): #값이 작다면 중간-1 부분만 고려
    return binary(first,value,start,mid-1)    


N=int(input())
first=list(map(int,input().split()))
M=int(input())
second=list(map(int,input().split()))
first.sort() ##이진탐색을 적용하려면 정렬되어 있어야함 


for i in range(M):
  start=0
  end=len(first)-1
  print(binary(first,second[i],start,end))

이진탐색을 적용한 코드.