求一个数列中元素值等于其下标的个数及其下标的值（T(i)=i）
要求时间复杂度为O（logn）
主要思路
1、考虑到时间复杂度，所以优先选用二分搜索
2、一个数组a[]中，a[i]<i,那么i前面的所有元素都不符合要求；同样，当a[i]>i时，i后面所有元素都不符合要求
3、当a[i]=i时，个数加一，并且对其左右的元素分别进行二分搜索
4、累加递归过程中的个数，并记录对应下标值
主要函数
void BC (int *a, int *b, int left, int right) {//求数组a【left：right】中,元素等于其下标的个数count,并将符合要求的数存在数组b中
int mid = (left+right)/2;
if (a[left]>left && a[right]<right) return ;
if (left == right) return ;
if (a[mid] == mid) {
b[count++] = mid;
BC (a, b, left, mid);
BC (a, b, mid+1, right);
}
else if (a[mid] > mid) BC (a, b, left, mid);
else if (a[mid] < mid) BC (a, b, mid+1, right);
}
完整代码
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int count = 0;
void BC (int *a, int *b, int left, int right) {//求数组a【left：right】中,元素等于其下标的个数count,并将符合要求的数存在数组b中
int mid = (left+right)/2;
if (a[left]>left && a[right]<right) return ;
if (left == right) return ;
if (a[mid] == mid) {
b[count++] = mid;
BC (a, b, left, mid);
BC (a, b, mid+1, right);
}
else if (a[mid] > mid) BC (a, b, left, mid);
else if (a[mid] < mid) BC (a, b, mid+1, right);
}
int main ()
{
int a[99], b[99], left, right;
int n, i;
cin >> n;
for (i=0; i<n; i++)
cin >> a[i];
left = 0;
right = n;
BC (a, b, left, right);
cout << count << endl;
for (i=0; i<count; i++)
cout << b[i];
return 0;
}
Example
5
-2 -1 2 6 7enter
输出结果：
1
2
