[Algorithm 풀이] 이진 탐색

문제

n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다.

출력

각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다.

---

CODE

import sys
n , q = map(int, input().split(" "))
nums = list(map(int,sys.stdin.readline().split()))
ques = list(map(int,sys.stdin.readline().split()))
def binary(nums, i, start, end):
  if start > end: # start > end 될때까지 탐색(끝까지 탐색)
    return False
  mid = (start+end)//2
  if nums[mid] == i:
    return True
  elif nums[mid] > i: #i=4
    return binary(nums, i, start, mid-1) #end 감소 재귀
  else:
    return binary(nums, i, mid+1, end) #start 증가 재귀
for i in ques:
  res = binary(nums, i , 0, len(nums)-1) #len(nums)-1 : 9
  if res == True:
    print('YES')
  else:
    print('NO')

 

 ⭐️ SOLUTION ⭐️

1. 반으로 쪼개 가며 탐색. 비교하고자 하는 숫자와 비교한 후 start, end 조정.

2. "현재 숫자(nums) > 비교 숫자(ques)" 면 end point를 1 감소.

3. "현재 숫자 < 비교 숫자" 면 start point를 1 증가.

4. 현재 숫자 == 비교 숫자 될때까지 탐색. 있으면 True 반환.

5. 탐색해도 같지 않으면 비교 숫자가 현재 숫자 안에 없는 것임. False 반환.