이번 글에서는 주어진 배열에서 고정점(fixed point)을 찾는 방법을 알아보겠습니다. 여기서 고정점이란 배열 요소의 값이 자신의 인덱스와 동일한 경우를 의미합니다. 예를 들어 인덱스 3 위치의 값이 3이라면 그 요소가 고정점입니다. 프로그램은 고정점이 존재하면 해당 값을 반환하고, 존재하지 않으면 -1을 반환합니다. 배열에는 음수도 포함될 수 있으며, 모든 데이터 요소는 정렬되어 있다고 가정합니다.
이 문제는 이진 탐색(binary search) 기법을 활용하면 O(log n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 탐색 과정은 다음과 같습니다.
- 먼저 중간 요소가 고정점인지 확인합니다. 즉, 인덱스(mid)와 그 위치의 값(arr[mid])이 같은지 비교합니다.
- 같다면 해당 값을 곧바로 반환합니다.
- 같지 않다면 두 가지 경우를 고려합니다. 중간 요소의 인덱스가 그 위치의 값보다 크다면(mid > arr[mid]) 오른쪽 영역에 고정점이 있을 가능성이 있으므로 오른쪽을 탐색하고, 그렇지 않다면 왼쪽 영역을 탐색합니다.
배열이 오름차순으로 정렬되어 있기 때문에 이러한 조건 분기가 성립하며, 탐색 범위를 절반씩 줄여나갈 수 있습니다.
예제 코드
#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
if(right >= left){
int mid = (left + right)/2; /*low + (high - low)/2;*/
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return getFixedPoint(arr, (mid + 1), right);
else
return getFixedPoint(arr, left, (mid -1));
}
return -1;
}
int main() {
int arr[] = {-10, -1, 0, 3, 10, 11, 9, 50, 56};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
}실행 결과
Fixed Point: 3
위 예제에서 배열 {-10, -1, 0, 3, 10, 11, 9, 50, 56}을 보면, 인덱스 3 위치의 값이 3으로 서로 일치합니다. 따라서 프로그램은 고정점인 3을 출력합니다. 만약 배열에 고정점이 하나도 없었다면 함수는 -1을 반환했을 것입니다.