数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 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
更新于: 2019-10-24
191 次查看
广告