C++で許可されている重複を含む配列内の固定小数点を検索します

ここでは、特定の配列で固定小数点を見つける方法を説明します。配列では、値がそのインデックスと同じである場合、1つの要素は固定小数点として示されます。このプログラムは、存在する場合は値を返し、そうでない場合は-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