n개의 요소를 가진 정렬된 배열 A가 있다고 가정해 보겠습니다. 우리의 목표는 주어진 정수(목표값)와 가장 가까운 값을 찾는 것입니다. 배열에는 중복된 값이나 음수가 포함될 수 있습니다.
예를 들어, 배열이 [2, 5, 6, 7, 8, 8, 9]이고 목표 숫자가 4라면, 4와 가장 가까운 요소는 5입니다.
문제 해결 접근 방식
가장 단순한 방법은 배열을 처음부터 끝까지 순회하면서 각 요소와 목표값 사이의 절대 차이를 기록하고, 마지막에 절대 차이가 가장 작은 요소를 반환하는 것입니다. 하지만 이 방법은 O(n)의 시간 복잡도를 가집니다.
배열이 이미 정렬되어 있다는 조건을 활용하면 이진 탐색(Binary Search)을 적용할 수 있으며, 이 경우 시간 복잡도를 O(log n)까지 줄일 수 있어 훨씬 효율적입니다.
이진 탐색 과정에서 목표값과 정확히 일치하는 요소를 찾으면 그 값을 바로 반환하고, 그렇지 않다면 탐색 범위가 좁혀지는 지점 근처의 두 인접 요소 중 목표값에 더 가까운 쪽을 선택합니다.
예제 코드
#include<iostream>
#include<list>
using namespace std;
int getNearest(int x, int y, int target) {
if (target - x >= y - target)
return y;
else
return x;
}
int getNearestElement(int arr[], int n, int target) {
if (target <= arr[0])
return arr[0];
if (target >= arr[n - 1])
return arr[n - 1];
int left = 0, right = n, mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] == target)
return arr[mid];
if (target < arr[mid]) {
if (mid > 0 && target > arr[mid - 1])
return getNearest(arr[mid - 1], arr[mid], target);
right = mid;
} else {
if (mid < n - 1 && target < arr[mid + 1])
return getNearest(arr[mid], arr[mid + 1], target);
left = mid + 1;
}
}
return arr[mid];
}
int main() {
int arr[] = { 2, 5, 6, 7, 8, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int target = 4;
cout << "Nearest element of " << target << " is: " << getNearestElement(arr, n, target);
}코드 설명
- getNearest(): 두 후보 값 x, y 중 목표값에 더 가까운 값을 반환하는 보조 함수입니다.
- 경계 처리: 목표값이 배열의 첫 번째 요소보다 작거나 같으면 첫 번째 요소를, 마지막 요소보다 크거나 같으면 마지막 요소를 즉시 반환합니다.
- 이진 탐색: mid 위치의 값이 목표값과 일치하면 바로 반환하고, 목표값이 mid 값보다 작으면 왼쪽 구간에서, 크면 오른쪽 구간에서 인접한 두 요소를 비교하여 가장 가까운 값을 결정합니다.
실행 결과
Nearest element of 4 is: 5
위 실행 결과에서 확인할 수 있듯이, 목표값 4에 가장 가까운 배열의 요소는 5입니다. 이 알고리즘은 정렬된 배열에서 O(log n) 시간 안에 최근접 값을 찾을 수 있어 대용량 데이터에서도 효율적으로 동작합니다.