在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