题目描述：

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

 

解析：

很多解法的时间复杂度都停留在O(n)，下面的解法 仍为二分查找法 只不过 对应题目做了相应的改进 时间复杂度为O(log₂n)

 

1.思路：(画图实际上更直观看出来思路，读者试着自己画出图来对应分析)

设数组a[start]~a[end],mid = (start + end) / 2 在进行二叉查找时，待查找数肯定会在变量mid的两侧，其中mid的取值主要有以下几情况，

第一种为a[mid] < a[start] 说明此时mid对应的数字在最大数的左边， 第二种为a[start]  > a[end] 说明此时mid对应的数字在最大数的右边，这两种情况对应不同的判断计算方法，详见下面的代码，其他情况不是违反题意就是容易得出结果。

 

2.代码

#include 
     
      using namespace std;int find(int *a ,int x, int max){    int start = 0, end = max - 1;    while(start < end - 1)    {        int mid = start + (end - start)/2;        if(a[start] == x)            return start;        if(a[end] == x)            return end;        if(a[mid] == x)            return mid;        if(a[mid] < a[start] )        {            if( x < a[start] && x > a[mid])                end = mid ;            else                start = mid ;        }        else if(a[mid] > a[end])        {            if( x > a[end] && x < a[mid])                start = mid ;            else                end = mid ;        }        else        {            if (x != a[mid])                return -1;            else                return mid;        }  }  return -1;}int main(){    int a[10] = {
   4, 3, 2, 1, 10 ,9, 8,7, 6, 5};    int index = find(a, 8, 10);    cout <<  "index:" << index << endl;    return 0;}
     

 

 

3.执行效果：