二分查找的扩展问题，循环数组中查找某一数字
问题：对已排好序的数组A，一般来说可用二分查找 可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9}，试在这样的数组中找一元素x，看看是否存在。请写出你的算法，必要时可写伪代码，并分析其空间、时间复杂度。
思路：首先可先确定循环数组最大元素的位置，例如，给定的例子当中最大元素为25，下标为3，确定了最大元素的位置之后，可以根据要查找的元素与A[0]的大小关系来确定在数组的哪一部分查找，确定最大元素位置的过程本身也二分查找的一个扩展问题，思想比较简单，一下给出实现代码，相信大家都能轻松理解。
#include<iostream>using namespace std;int bin_search(int *data,int len,int key);int main(){int len;cin>>len;//输入数组data的长度lenint *data=new int[len];for(int i=0;i<len;i++)//输入数组data的元素值cin>>data[i];int key;cin>>key;//输入要查找的数字int index=bin_search(data,len,key);if(index==-1)cout<<"Can not find "<<key<<endl;elsecout<<"data["<<index<<"]="<<key<<endl;delete []data;return 0;}int bin_search(int *data,int len,int key){if(data==NULL||len<=0)return -1;int start,mid,end;start=0;end=len-1;mid=end;while(data[start]>=data[end]){if(end-start==1)//找到了循环数组中最大的元素的位置start{mid=start;break;}mid=start+(end-start)/2;if(data[mid]==data[start]&&data[mid]==data[end])//mid,start,end三个下标对应的元素相等，只通过线性遍历确定最大元素的位置{for(int i=start;i<=end;i++){if(data[i]>data[i+1])mid=i;}break;}else if(data[start]<=data[mid])start=mid;elseend=mid;}if(key==data[0])return 0;else if(key<data[0]){start=mid+1;end=len-1;int index;while(start<=end){index=start+(end-start)/2;if(data[index]==key)return index;else if(data[index]>key)end=index-1;elsestart=index+1;}return -1;}else{start=0;end=mid;int index;while(start<=end){index=start+(end-start)/2;if(data[index]==key)return index;else if(data[index]>key)end=index-1;elsestart=index+1;}return -1;}}时间复杂度为O(logn),空间复杂度为O(1).