이 문제에서는 무한히 이어지는 정렬된 숫자 배열이 주어집니다.
우리의 과제는 정렬된 무한 배열 안에서 특정 요소의 위치(인덱스)를 찾는 것입니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력
arr[] = {2, 4, 6, 8, 9, 12, 14, 17, ...}, ele = 9출력
4
배열은 계속 이어지지만 끝 지점을 알 수 없다는 점이 핵심입니다. 즉, 일반적인 방식으로 배열의 크기를 먼저 확인할 수 없습니다.
해결 접근 방법
정렬된 배열에서 요소를 효율적으로 찾으려면 이진 탐색(Binary Search)을 사용하는 것이 가장 좋습니다. 하지만 배열의 끝 지점(end point)을 알 수 없기 때문에 알고리즘을 약간 수정해야 합니다.
절차는 다음과 같습니다.
1단계: 시작 포인터(start)를 첫 번째 위치(0)로 고정하고, 끝 포인터(end)를 두 번째 위치(1)로 설정합니다.
2단계: 끝 포인터가 가리키는 값을 확인하고, 그 값이 찾고자 하는 값(key)보다 작으면 끝 포인터를 2배씩 늘려가며 범위를 확장합니다. 이때 시작 포인터는 확장 전 끝 포인터의 위치로 갱신합니다.
3단계: 끝 포인터의 값이 찾으려는 요소보다 커지면, 그 시점의 [start, end] 구간 내에서 일반적인 이진 탐색을 수행하여 요소의 위치를 찾습니다.
이 방식은 '지수적 탐색(Exponential Search)'과 유사하며, 요소가 위치한 인덱스를 p라고 할 때 시간 복잡도는 O(log p)입니다. 배열이 아무리 커져도 목표 위치 근처만 탐색하므로 매우 효율적입니다.
구현 예제 코드
아래는 위 해결 방법이 실제로 동작하는 모습을 보여주는 C++ 프로그램입니다.
#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
if (end >= start) {
int mid = start + (end - start)/2;
if (arr[mid] == ele)
return mid;
if (arr[mid] > ele)
return binarySearch(arr, start, mid-1, ele);
return binarySearch(arr, mid+1, end, ele);
}
return -1;
}
int findPos(int arr[], int value) {
int start = 0, end = 1;
while (arr[end] < value) {
start = end;
end = 2*end;
}
return binarySearch(arr, start, end, value);
}
int main(){
int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
int index = findPos(arr, 9);
if (index == -1)
cout<<"Element not found!";
else
cout<<"Element found! index = "<<index;
return 0;
}출력 결과
Element found! index = 5
코드 설명
findPos 함수는 끝 포인터를 2배씩 확장하며 목표 값보다 크거나 같은 첫 번째 지점을 찾아 탐색 범위를 결정합니다. 이후 binarySearch 함수가 해당 범위 안에서 재귀적으로 이진 탐색을 수행합니다.
요소를 찾으면 해당 인덱스를 반환하고, 찾지 못하면 -1을 반환하여 "Element not found!" 메시지를 출력합니다. 위 예제에서는 값 9가 인덱스 5에 위치하므로 올바른 결과가 출력됩니다.