题目：一个数组是由一个递增数列右移若干位形成的，比如{
   4,5,1,2,3}是由{
   1,2,3,4,5}左移两位形成的，在这种数组中查找某一个数。

这道题其实是前面介绍的一道题目： 的一个变种。

解题思路如下：

1. 首先通过“”这道题目中获取元素分裂点，时间复杂度为O(log(n))
2. 因为旋转数组是由递增数组右移得到，因此旋转数组中的第一个元素是整个数组的中间元素，比较待查找元素与第一个元素，如果待查找元素大于等于第一个元素，表明待查找元素在前半段有序数组中；如果不是这待查找元素在后半段数组中。
3. 判断待查找元素所在的有序数组以后，我们通过一个简单的二分查找就可以找出元素所在位置，时间复杂度也是O(log(n))
4. 总是时间复杂度为2个O(log(n))，所以时间复杂度还是O(log(n))。

代码实例

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;//函数声明int getSplitIndex(int arry[],int len);//获取分裂点坐标int BinarySearch(int arry[],int len,int value);//二分查找通用算法int FindNumInRotatedArry(int arry[],int len,int value);//查询元素位置//二分查找算法，不使用递归，如果存在返回数组位置，不存在则返回-1int BinarySearch(int arry[],int start,int end,int value){    //如果传入的数组为空或者数组长度<=0那么就返回-1。防御性编程    if(arry==NULL||start>end)        return -1;    while(start<=end)//判断清是否有=    {        int mid=start+(end-start)/2;        if(arry[mid]==value)            return mid;        else if(value
          
           arry[start])        {            start=mid;        }    }    return -1;}int FindNumInRotatedArry(int arry[],int len,int value)//返回最小数的坐标{    if(arry==NULL||len<=0)        return -1;    int start=0;    int end=len-1;    int splitIndex=getSplitIndex(arry,len);//获取分裂点坐标    cout<<"分裂点坐标："<
           
            <
            
             =arry[start]) { end=splitIndex-1; return BinarySearch(arry,start,end,value); } else//否则在后半段查找 { start=splitIndex; return BinarySearch(arry,start,end,value); } return -1;}void main(){ int arry[]={ 4,5,1,2,3}; int len=sizeof(arry)/sizeof(int); int value=3; int index=FindNumInRotatedArry(arry,len,value); cout<<"查找数在数组中的位置："<
             
              <
             
            
           
          
         
        
       
      

程序输出结果：

分裂点坐标：2

查找数在数组中的位置：4

请按任意键继续. . .