在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