数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理
社会研究
时尚研究
法律研究在允许重复项的数组中找出固定点 (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
更新日期: 2019-10-24
126 次浏览
广告