求T(i)=i

求一个数列中元素值等于其下标的个数及其下标的值（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