数组跳跃遍历减少比较次数
这道题目找了一个同学一起想，后来发现题目是野路子来的，最后题目意思理解除了偏差，衰。。。。再次表示诚挚的抱歉，是我错了。。。不过正好拓宽了思路，也把另一种问法解决了
原题描述：
在相邻元素相差1的数组中查找某一特定元素第一次出现的位置(非遍历)
通过各种渠道传到我这里，就变成了：
数组A中任意两个相邻元素大小相差1，现给定这样的数组A和目标整数t，找出t在数组A中的位置。
我想先自己思考，于是也没细究题目，认为题目是指找出所有的t的index出来，如果元素不重复的话，那就太简单了，直接定位i=|t-a[0]|，如果是的话返回index，不是的话，直接退出循环说找不到了。
我已开始以为这个是在时间复杂度渐进意义上要从线性减少，首先想到的是对数，但是感觉又想不到对数复杂度的算法。
思考这种题目，感觉就是需要归纳一些性质出来，提高效率，不论能够降低时间复杂度，都至少可以减少次数吧。
性质1：如果两个元素a[i] a[j]的差和index差相等，那么之间的元素一定是从(a[i],a[j])之间逐个递增或递减，也即不可能出现等于a[i]或a[j]
性质2：相邻2个元素一定是奇偶性相反，所以如果当前t和i同奇偶性,则解不可能是i-1 i+1的话，也一定只可能是i+2，不可能是i+1, i+3,
所以针对这些性质，如果对于问题输出所有t的index的话，我有了下面的代码：
void FindXIndex(int* a, int n, int x)
{
int xi,j,tmp;
for(int i=0;i<n;i++)
{
if(a[i]==x)
{
xi=i;
break;
}
}
printf("%d ", xi);
while(abs(j-xi)>=2)
{
if(abs(a[j]-a[xi])==abs(j-xi))
break;
else if(a[j]==x)
{
printf("%d ", j);
if(xi<j)
{
tmp=xi, xi=j, j=tmp+1;
}
else
{
tmp=xi, xi=j, j=tmp-1;
}
}
else
{
if(xi<j) j--;
else j++;
}
}
return;
}
先从找到一个t的index，然后从另一端向这段搜索，如果存在差值等于index差值，则直接返回，因为中间不可能还有t了，也即区间收缩到0了。所以循环的条件是区间长度是否大于1，如果等于1的话也不用了，只有一个元素，必为已经搜过的xi，
且程序里a[xi]=t的。然后j始终从当前值向xi靠近，注意根据和xi大小关系，判断++ 还是 —
这个算法是输出所有的index，后来看了下题目，原始不需要全部，好吧，自己做了一道新题。。。。
如果是只要返回任意一个，当然效率尽可能高，也即如何最快找到t的一个index，可以先从一端开始，例如0，先和a[0]比较，|t-a[0]|+0,是可能的t的位置，而且从(0 , |t-a[0]|+0)之间 是不可能出现解的，因为最快的增长(下降)速度才能使得边界达到t，
如果t=a[0]的话，0也可能, 所以第一步就大胆往前跳，同时第一步跳到的一定是奇偶性和t一致的点，所以改点两边的点和t奇偶性反，不可能是解，于是乎可以大胆的两步一跳。
int findpos(int a[],int n,int v)
{
for(int i = abs(v-a[0]); i < n; i+=2)
if(a[i] == v)
return i;
return -1;
}
代码来自：http://blog.csdn.net/u010590166/article/details/17250653#cpp
后来发现这个其实还不够优，看到下面童鞋的代码，好像更优
http://m.blog.csdn.net/blog/pein0119/11678997
不止是第一步跳跃，而是每次都是跳跃前进，直到找到或者遍历完位置，
i=abs(a[i]-t);
通过这句代码来实现的。
另外再加深一下印象，C语言的scanf 后面参数是地址， printf后面是变量，为什么是这样呢？思考一下原因更容易记住用法，因为输入是要把变量从键盘输到内存某个地址去，自然需要地址了，而打印只需要这个值传过来就行了，例如输出缓冲区，
实际上C++已经封装好了一切，所以不需要我们考虑，一律都是变量名了。C语言会更底层一些。