이진 탐색으로 배열에서 가장 가까운 값 찾기 - 값이 존재하지 않을 때는 어떻게 할까?

Об этом предложении

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 대표적인 탐색 알고리즘이다. 보통은 다음과 같이 설명한다. 찾으려는 값과 배열의 중간값을 비교하면서 탐색 범위를 절반씩 줄여 나간다. 시간 복잡도는 O(log N) 이다. 그런데 문제를 풀다 보면 단순히 값의 존재 여부 만 필요한 경우보다 조금 더 까다로운 상황을 만나게 된다. 예를 들어 다음과 같은 배열이 있다고 하자. int[] arr = {10, 20, 30, 40, 50}; 여기서 30 을 찾는 것은 어렵지 않다. 하지만 26 을 찾으려고 했는데 배열에 26 이 없다면? 이번에는 단순히 -1 을 반환하는 것이 아니라, 배열에 정확한 값이 없다면 가장 가까운 값을 반환하고 싶다. 라는 조건이 생긴다. 추가로 거리가 같다면 더 큰 값을 선택한다 고 해보자. target = 25 20과의 거리 = 5 30과의 거리 = 5 → 거리가 같으므로 30 선택 이 문제를 이진 탐색으로 어떻게 해결할 수 있을까? 1. 가장 단순한 방법: 전체 배열 탐색 가장 먼저 떠올릴 수 있는 방법은 배열 전체를 순회하면서 target과의 거리를 계산하는 것이다. public int findClosest(int[] arr, int target) { int closest = arr[0]; for (int value : arr) { int currentDistance = Math.abs(value - target); int closestDistance = Math.abs(closest - target); if (currentDistance < closestDistance || (currentDistance == closestDistance && value > closest)) { closest = value; } } return closest; } 이 방법은 구현도 쉽고 배열이 정렬되어 있을 필요도 없다. 하지만 모든 원소를 확인해야 하므로 시간 복잡도는 O(N) 이다. 배열이 이미 정렬되어 있다면 이 정렬 상태를 이용해서 더 빠르게 찾을 수 있다. 2. 이진 탐색이 끝난 뒤의 left , right 일반적인 이진 탐색을 살펴보자. int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } 보통은 여기서 값을 찾지 못하면 -1 을 반환한다. 하지만 여기서 중요한 점이 하나 있다. 탐색이 실패했을 때의 left 와 right 에는 의미가 있다. 예를 들어 arr = [10, 20, 30, 40, 50] target = 26 이라고 해보자. 이진 탐색이 끝나면 두 포인터는 다음 위치에 놓이게 된다. right left ↓ ↓ [10, 20, 30, 40, 50] 실제로는 20 < 26 < 30 right → 20 left → 30 즉 일반적인 경우라면 탐색 종료 후 다음 관계가 성립한다. arr[right] < target < arr[left] 따라서 가장 가까운 값을 찾기 위해서는 배열 전체를 볼 필요가 없다. arr[right] 와 arr[left] 두 개만 비교하면 된다. 3. 가장 가까운 값을 찾는 이진 탐색 이를 코드로 만들면 다음과 같다. public int binarySearchClosest(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } int leftDistance = arr[left] - target; int rightDistance = target - arr[right]; return leftDistance <= rightDistance ? left : right; } 거리까지 같다면 더 큰 값을 선택하고 싶으므로 leftDistance <= rightDistance 일 때 left 를 선택한다. 오름차순 배열에서는 arr[left] 가 arr[right] 보다 크기 때문이다. 하지만 이 코드에는 문제가 있다. 4. target이 배열 범위를 벗어나는 경우 다음 입력을 생각해보자. arr = [10, 20, 30] target = 5 이진 탐색이 끝나면 left = 0 right = -1 이 되므로, arr[right] 에서 ArrayIndexOutOfBoundsException 가 발생한다. 반대의 경우도 마찬가지다. arr = [10, 20, 30] target = 40 이면 탐색 종료 후 left = 3 right = 2 가 되면서, arr[left] = arr[3] 을 접근하게 되어 ArrayIndexOutOfBoundsException 이 발생한다. 그래서 경계 처리가 필요하다. 5. 경계까지 처리한 구현 public int binarySearchClosest(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // target이 배열의 최솟값보다 작은 경우 if (right < 0) { return left; } // target이 배열의 최댓값보다 큰 경우 if (left >= arr.length) { return right; } int leftDistance = arr[left] - target; int rightDistance = target - arr[right]; // 거리가 같으면 더 큰 값 선택 return leftDistance <= rightDistance ? left : right; } 이제 다음 세 가지 경우를 모두 처리할 수 있다. target < 배열의 최솟값 배열 내부에 target이 위치 target > 배열의 최댓값 시간 복잡도는 그대로 O(log N) 이다. 6. Arrays.binarySearch() 를 사용하면? Java에는 이미 이진 탐색을 구현한 메서드가 있다. Arrays.binarySearch(arr, target); 값이 존재하면 해당 인덱스를 반환한다. int[] arr = {10, 20, 30}; Arrays.binarySearch(arr, 20); // 1 그런데 값이 존재하지 않을 경우 단순히 -1 을 반환하지 않는다. 예를 들어 target이 25 라면 [10, 20, 30] ↑ 25가 들어갈 위치 삽입 위치는 2 다. Arrays.binarySearch() 는 다음 값을 반환한다. -(삽입 위치) - 1 즉 -(2) - 1 = -3 이다. 반환값에서 삽입 위치를 다시 얻으려면 int insertionPoint = -(result + 1); 을 사용하면 된다. 예를 들어 int result = Arrays.binarySearch(arr, 25); if (result < 0) { int insertionPoint = -(result + 1); } 이 insertionPoint 는 곧 target 이상인 값이 처음 등장할 위치 와 같다. 7. 사실 필요한 것은 "가장 가까운 값"보다 삽입 위치다 여기서 한 단계 더 생각해볼 수 있다. 가장 가까운 값을 직접 찾으려고 하기보다 먼저 target이 정렬 순서를 유지하면서 들어갈 위치가 어디인가? 를 찾는 것이 더 일반적인 접근이다. 예를 들어 arr = [10, 20, 30, 40] target = 27 이라면 [10, 20 | 27 | 30, 40] ↑ insertion point 삽입 위치는 2 다. 그러면 자연스럽게 후보는 left = insertionPoint - 1 right = insertionPoint 가 된다. 즉 20 ← 27 → 30 두 값만 비교하면 된다. 이 개념이 lower bound 와 연결된다. 8. Lower Bound Lower Bound는 정렬된 배열에서 target 이상인 값이 처음 등장하는 위치 를 찾는다. Java로 직접 구현하면 다음과 같다. private int lowerBound(int[] arr, int target) { int left = 0; int right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } 일반적인 이진 탐색과 가장 눈에 띄는 차이는 int right = arr.length; 이다. arr.length - 1 이 아니라 arr.length 까지 탐색 범위에 포함한다. 왜냐하면 target이 배열의 모든 값보다 클 경우 [10, 20, 30 | target] ↑ index 3 처럼 반환값이 실제 배열 인덱스를 넘어선 arr.length 가 될 수도 있기 때문이다. 9. Lower Bound를 이용한 가장 가까운 값 탐색 이를 이용하면 가장 가까운 값 찾기도 깔끔해진다. public int findClosestIndex(int[] arr, int target) { int right = lowerBound(arr, target); int left = right - 1; if (left < 0) { return right; } if (right >= arr.length) { return left; } int leftDistance = target - arr[left]; int rightDistance = arr[right] - target; // 거리가 같으면 큰 값인 right 선택 return rightDistance <= leftDistance ? right : left; } private int lowerBound(int[] arr, int target) { int left = 0; int right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } 개인적으로는 처음 작성한 "값을 찾는 이진 탐색을 변형하는 방식"보다 이 구조가 더 이해하기 쉽다. 우리가 실제로 원하는 것은 먼저 target의 위치 를 찾고, 그 다음 target 왼쪽 값 과 target 오른쪽 값 을 비교하는 것이기 때문이다. 10. 가장 가까운 값을 여러 개 찾고 싶다면? 여기서 한 단계 더 확장할 수 있다. 예를 들어 다음 배열에서 arr = [1, 2, 3, 4, 5, 6, 7] target = 4 target에 가까운 순서대로 모든 값을 나열하고 싶다고 해보자. 거리만 보면 왼쪽 3 → 거리 1 2 → 거리 2 1 → 거리 3 오른쪽은 4 → 거리 0 5 → 거리 1 6 → 거리 2 7 → 거리 3 가 된다. 즉 target 기준으로 배열을 나누면 양쪽이 각각 이미 거리순으로 정렬된 상태가 된다. 왼쪽 후보: 3, 2, 1 오른쪽 후보: 4, 5, 6, 7 따라서 두 포인터를 두고 가까운 값부터 하나씩 선택하면 된다. int right = lowerBound(numlist, n); int left = right - 1; 그리고 while (left >= 0 && right < numlist.length) { int leftDistance = n - numlist[left]; int rightDistance = numlist[right] - n; if (rightDistance <= leftDistance) { result[current++] = numlist[right++]; } else { result[current++] = numlist[left--]; } } 처럼 두 후보군을 병합할 수 있다. 이 구조는 Merge Sort의 merge 단계와 상당히 비슷하다. 11. 단순 이진 탐색에서 얻은 중요한 관찰 이번 문제를 풀면서 이진 탐색을 단순히 "정렬된 배열에서 값을 빠르게 찾는 알고리즘" 으로만 이해하면 아쉽다는 생각이 들었다. 이진 탐색이 실패했을 때도 정보는 남아 있다. right < left 가 된다는 것은 단순히 값을 찾지 못했다 는 의미만 있는 것이 아니다. 일반적인 경우 arr[right] < target < arr[left] 라는 위치 관계를 얻을 수 있다. 그리고 이 정보는 가장 가까운 값 찾기 삽입 위치 찾기 Lower Bound Upper Bound 특정 조건을 처음 만족하는 위치 찾기 투 포인터와 결합한 탐색 등으로 확장할 수 있다. 정리 정렬된 배열에서 정확한 값이 존재하지 않을 때 가장 가까운 값을 찾고 싶다면 전체 배열을 순회할 필요가 없다. 핵심은 target이 들어갈 위치( InsertionPoint )를 찾는 것이다. target ↓ ... arr[left] | arr[right] ... 그리고 target의 바로 왼쪽과 오른쪽 값만 비교하면 된다. 전체 흐름을 정리하면 다음과 같다. 정렬된 배열 ↓ 이진 탐색 ↓ target의 삽입 위치 탐색 ↓ 왼쪽 후보 / 오른쪽 후보 ↓ 두 값의 거리 비교 ↓ 가장 가까운 값 선택 단순히 하나의 값을 찾는 문제라면 시간 복잡도는 O(log N) 이다. 이번 문제를 통해 가장 크게 얻은 것은 이진 탐색의 구현 자체보다 값을 찾지 못했을 때의 left와 right도 중요한 정보를 가지고 있다 는 점이었다. 이진 탐색은 "정답이 있는 위치"를 찾는 알고리즘으로만 보기보다, 정렬된 탐색 공간에서 조건의 경계를 찾는 알고리즘 으로 이해하면 훨씬 다양한 문제에 활용할 수 있다.