求一個(gè)數(shù)列中元素值等于其下標(biāo)的個(gè)數(shù)及其下標(biāo)的值（T(i)=i）
要求時(shí)間復(fù)雜度為O（logn）

主要思路

1、考慮到時(shí)間復(fù)雜度，所以優(yōu)先選用二分搜索
2、一個(gè)數(shù)組a[]中，a[i]<i,那么i前面的所有元素都不符合要求；同樣，當(dāng)a[i]>i時(shí)，i后面所有元素都不符合要求
3、當(dāng)a[i]=i時(shí)，個(gè)數(shù)加一，并且對(duì)其左右的元素分別進(jìn)行二分搜索
4、累加遞歸過(guò)程中的個(gè)數(shù)，并記錄對(duì)應(yīng)下標(biāo)值

主要函數(shù)

void BC (int *a, int *b, int left, int right) {//求數(shù)組a【left：right】中,元素等于其下標(biāo)的個(gè)數(shù)count,并將符合要求的數(shù)存在數(shù)組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) {//求數(shù)組a【left：right】中,元素等于其下標(biāo)的個(gè)數(shù)count,并將符合要求的數(shù)存在數(shù)組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
輸出結(jié)果：
1
2