[알고리즘] K와 가장 가까운 수 구하기

문제

오름차순으로 정렬된 n(2이상 100,000이하 정수)개의 정수(1,000,000,000이하 양의 정수) 중 K(양의 정수)와 가장 가까운 정수를 찾는 프로그램을 작성하시오. K와 가장 가까운 정수가 여러 개일 경우, 이들 중 작은 수를 출력하시오.
요구 조건: 이진 탐색(binary search)을 이용해야 한다.

입력 예시 1

5 // n
20 30 40 55 60 // n개의 정수
36 // K

출력 예시 1

40

입력 예시 2

13
20 30 40 55 60 70 75 80 85 90 91 93 100
92

출력 예시 2

92

나의 풀이

n = int(input())
num_list = list(map(int, input().split()))
K = int(input())

def binary_search(n, num_list, K):  # 일반적인 이진탐색 함수
   num_list.sort()  # 정렬
   left = 0
   right = len(num_list) - 1
   result = 0  # 마지막에 return할 result 값을 선언함
   while left <= right:  # left가 right보다 클 때까지 진행하는 while문을 돌림
       if 2 <= n <= 100000:
           mid = (left + right) // 2  # 중간값은 두개를 더한 것을 2로 나눈 몫
           if K == num_list[mid]:  # 구하고자 하는 K가 리스트의 중간값과 같다면 K를 리턴하고 종료
               return num_list[mid]
           elif K < num_list[mid]:  # elif와 else문은 일반적인 이진 탐색과 크게 다르지 않음
               right = mid - 1
           else:
               left = mid + 1

   if K not in num_list:  # left가 right보다 커졌을 때 while문이 종료됨. num_list에 K가 없을 경우에
       low = abs(K - num_list[right])  # 현재 right의 인덱스가 더 작으므로, 작은 인덱스쪽의 절대값을 K - num_list[right]으로 줬고 이를 low로 선언함
       high = abs(num_list[left] - K)  # 현재 left의 인덱스가 더 크므로, 큰 인덱스쪽의 절대값을 num_list[left] - K로 줬고 이를 high로 선언함

       if low <= high:  # 더 작은 인덱스의 절대값이 더 큰 인덱스의 절대값보다 "같거나" 작을 때:
           result = num_list[right]    # 결과값 result에 num_list[right]을 부여함
       else:  # 더 작은 인덱스의 절대값이 더 큰 인덱스의 절대값보다 클 때:
           result = num_list[left]  # 결과값 result에 num_list[left]을 부여함

       return result # 최종 결과값 result를 반환합니다.

print(binary_search(n, num_list, K))

이진 탐색에서 살짝 꼬았던 문제로, K의 값이 기존 배열에 없을 경우 절대값이 더 작은 쪽의 값을 구하며 절대값이 같은 원소가 있을 경우 그들 중에 작은 값을 출력하는 문제였다. while문을 마치면 left가 right보다 크게 되었고, 인덱스 또한 그에 맞게 수정하였다.