升序数组两两不相等

题目：给定一个排好升序的数组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)。