题目：给定一个排好升序的数组A[1],A[2],… A[n]，其元素的值两两都不相等。请设计一个高效算法，找出其中所有A[]=i的下标，并分析其复杂度。
算法分析：一个升序且值都不相等的数组，如果第一个数大于右下标（数组最后一个数的下标），或最后一个数小于左下标，则这个数组里一定没有满足题意的数。
- 对于int型数组，可以使用二分法，如果a[mid]>mid+1，由于数组为整型且递增，没有相同的元素，因此右半段一定都不符合题意，因此只需要在左边继续查找。a[mid]<mid+1时同理，只需要在右半段查找。而a[mid]==mid+1时，左右两边都有可能有答案，因此还需要在左右两边继续查找。
- 对于浮点型数组，无论a[mid]和mid+1的关系如何，都无法缩小查找范围，左边和右边都有可能存在答案。所以考虑a[mid]和边界的关系：如果a[mid]<left+1或a[left]>mid+1，显然答案就在右半段；如果a[mid]>right+1或a[right]<mid+1，答案就在左半段。否则，两边都有可能。
算法实现：
#include<iostream>
using namespace std;
const int n=5;
//void find(int a[n],int left,int right){
// if(left>right) return;
// if(a[left]>right+1||a[right]<left+1) return;//数组第一个数大于右下标，最后一个数小于左下标，显然无解。加1是因为题目中数组下标从1开始
// int mid=(right+left)>>1;
// if(a[mid]==mid+1){
// cout<<a[mid]<<" ";
// find(a,left,mid-1);
// find(a,mid+1,right);
// }else if(a[mid]>mid+1){//如果 a[mid]>mid+1，只有左半边有可能
// find(a,left,mid-1);
// }else{//如果 a[mid]<mid+1，只有右半边有可能
// find(a,mid+1,right);
// }
//}
void find2(double a[n],int left,int right){
if(left>right) return;
if(a[left]>right+1||a[right]<left+1) return;//数组第一个数大于右下标，最后一个数小于左下标，显然无解。加1是因为题目中数组下标从1开始
int mid=(left+right)>>1;
if(a[mid]<left+1||a[left]>mid+1){//答案在右半段
find2(a,mid+1,right);
}else if(a[mid]>right+1||a[right]<mid+1){//答案在左半段
find2(a,left,mid-1);
}else if(a[mid]==mid+1){
cout<<mid+1<<" ";
find2(a,mid+1,right);
find2(a,left,mid-1);
}else{
find2(a,mid+1,right);
find2(a,left,mid-1);
}
}
int main(){
// int a[n]={1,2,3,4,5};
// find(a,0,n-1);
double a[n]={1.1,2,3.1,4,5};
find2(a,0,n-1);
return 0;
}
对于int型数组：
复杂度分析：最坏时间复杂度为O(n)：可能每次a[mid]都等于mid+1，此时需要遍历整个数组；平均时间复杂度为O(logn)：平均情况下，T(n)=T(n/2)+O(1)；空间复杂度为O(logn)：递归调用的深度为logn。
对于浮点型数组：
复杂度分析：最坏时间复杂度为O(n)，平均时间复杂度为O(n)；空间复杂度为O(logn)。
