C++에서 허용되는 중복이 있는 배열에서 고정 소수점 찾기

여기서 우리는 주어진 배열에서 고정 소수점을 찾는 방법을 볼 것입니다. 배열에서 값이 인덱스와 같으면 하나의 요소가 고정 소수점으로 표시됩니다. 이 프로그램은 값이 있으면 값을 반환하고 그렇지 않으면 -1을 반환합니다. 배열에는 음수도 포함될 수 있습니다. 그리고 데이터 요소가 정렬됩니다. 여기에서 배열에 중복 요소가 허용됩니다.

여기서는 O(log n) 시간에 이 문제를 해결하기 위해 이진 검색 접근 방식을 사용합니다. 그러나 약간의 수정이 필요합니다. 일반 이진 검색을 사용하면 중복 요소에 대해 실패할 수 있습니다. 왼쪽을 확인하려면 min(mid – 1, midValue)부터 시작하고 오른쪽을 확인하려면 max(mid + 1, midValue)부터 시작해야 합니다.

예

#include<iostream>
using namespace std;
int getFixedPoint(int arr[], int left, int right) {
   if (right < left)
      return -1;
   int mid = (left + right) / 2;
   int midValue = arr[mid];  
   if (mid == arr[mid])
      return mid;
   int leftindex = min(mid - 1, midValue);
   int l = getFixedPoint(arr, left, leftindex);
   if (l >= 0)
      return l;
   int rightindex = max(mid + 1, midValue);
   int r = getFixedPoint(arr, rightindex, right);
   return r;
}
int main() {
   int arr[] = {-10, -5, 2, 2, 2, 3, 4, 7, 10, 12, 17};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Fixed Point: "<< getFixedPoint(arr, 0, n-1);
}

출력

Fixed Point: 2