题目:

数组A中任意两个相邻元素大小相差1,现给定这样的数组A和目标整数t,找出t在数组A中的位置。
如数组:[1,2,3,4,3,4,5,6,5],找到4在数组中的位置。

思路:

很明显,在数组中寻找某个数的复杂度为O(n),但在某些特殊数组中,可以通过寻找规律来减少比较次数。

上述数组的规律就是:相邻元素相差1,奇偶交替排列。

如果某个数A[i]等于要查找的数x,那么由于奇偶交替排列的关系,可以跳过下个数A[i+1],即i=i+2;

如果某个数A[i]不等于要查找的数x,那么由于相邻元素相差1,可以跳过x-A[i]的绝对值个数,即i=i+abs(x-A[i])

通过数组的规律来进行查找,可以减少一半以上的时间复杂度。

代码:

#include <iostream>

using namespace std;

void findX(int A[],int len,int x){
    int tmp;
    for(int i=0;i<len;){
        if(A[i]==x){
            cout<<i<<endl;
            i=i+2;
            continue;
        }
        tmp=x-A[i];
        i=i+(tmp>=0?tmp:-tmp);
    }
}

int main()
{
    int A[]={1,2,1,2,3,4,3,4,5};
    int len=sizeof(A)/sizeof(A[0]);
    int x=4;
    findX(A,len,x);
    return 0;
}