C ++の特定の配列で固定小数点（インデックスに等しい値）を検索します

ここでは、特定の配列で固定小数点を見つける方法を説明します。配列では、値がそのインデックスと同じである場合、1つの要素は固定小数点として示されます。このプログラムは、存在する場合は値を返し、そうでない場合は-1を返します。配列は負の数も保持できます。そして、データ要素が並べ替えられます。

ここでは、二分探索アプローチを使用して、O（log n）時間でこの問題を解決します。最初に、中間要素が固定小数点であるかどうかを確認し、はいの場合はそれを返します。そうでない場合は、中間要素のインデックスがインデックスの値よりも大きい場合、インデックスが大きい場合の2つの状況があります。 、次に、右側で固定点を取得する可能性があります。そうでない場合は、左側で固定点を取得する可能性があります。

例

#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