在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