在C ++中允许重复的数组中查找固定点
在这里，我们将看到如何在给定数组中找到固定点。在数组中，如果一个元素的值与其索引相同，则将其表示为固定点。该程序将返回该值（如果有），否则返回-1。该数组也可以容纳负数。然后对数据元素进行排序。这里，数组中允许重复的元素。
在这里，我们将使用二进制搜索方法在O（logn）时间内解决此问题。但是我们需要进行一些修改，如果使用常规的二进制搜索，那么对于重复的元素它可能会失败。要检查左边，我们必须从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