在左移的递减数组中查找某数 【微软面试100题 第四十八题】

题目要求：

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

题目分析：

　　方法1 逐个查找，遍历一遍数组，时间复杂度O(N).

　　方法2 二分查找，时间复杂度O(logN).具体分析见下图：

代码实现：

#include <iostream>

using namespace std;
int Helper(int a[],int k,int s,int t);
int FindKInArray(int a[],int k,int n);
int main(void)
{
    int a[] = {4,3,2,1,6,5};
    
//    int Pos = FindKInArray(a,3,6);
//    int Pos = FindKInArray(a,6,6);
    int Pos = FindKInArray(a,7,6);
    if(Pos==-1)
        cout << "没有找到" << endl;
    else
        cout << "找到，在a[" << Pos << "]中" << endl;
    return 0;
}
//如果找到，就返回在数组中的位置,没有找到就返回-1
int FindKInArray(int a[],int k,int n)
{
    return Helper(a,k,0,n-1);
}
int Helper(int a[],int k,int s,int t)
{
    if(s>t)
        return -1;
    int mid;
    mid = s+(t-s)/2;
    if(a[mid]==k)
        return mid;
    if(a[s]>a[mid])
    {
        if(k<=a[s] && k>a[mid])
            return Helper(a,k,s,mid-1);
        else
            return Helper(a,k,mid+1,t);
    }
    else
    {
        if(k<a[mid] && k>=a[t])
            return Helper(a,k,mid+1,t);
        else
            return Helper(a,k,s,mid-1);
    }
}