C++의 주어진 배열에서 고정 소수점(인덱스와 동일한 값) 찾기

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

여기서는 O(log n) 시간에 이 문제를 해결하기 위해 이진 검색 접근 방식을 사용합니다. 처음에는 중간 요소가 고정 소수점인지 여부를 확인하고, 그렇다면 반환하고, 그렇지 않으면 중간 요소의 인덱스가 인덱스의 값보다 크면 인덱스가 크면 두 가지 상황이 발생합니다. , 그러면 오른쪽에서 고정 소수점을 얻을 기회가 있고, 그렇지 않으면 왼쪽에서 고정 소수점을 얻을 수 있습니다.

예시

#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