在移位数组中查找数

题目描述：

一个数组是由一个递减数列左移若干位形成的，比如{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 <iostream>

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.执行效果：