在相邻连个数相差为1或-1的数组中寻找给定值

这道好像是今年的一道面试题：

给定一个数组，其中相邻两个值之间的差值为1，或者-1,现在要求找出给定的值num，要求效率越高越好。

这道题最显然的做法是从头到尾扫描一遍，然后找出来。当然如果这么简单就不会是面试题了。

下面我们给一个更加有效的方法：

数组第一个数为array[0], 要找的数为y，设t = abs(y - array[0])。由于每个相邻的数字之差的绝对值为1。故第t个位置之前的数肯定都比y小。因此直接定位到array[t]，重新计算t，t = abs(y – array[t])，再重复上述步骤即可。这种算法主要利用了当前位置的数与查找数的差来实现跨越式搜索。算法效率要比遍历数组的算法要高一些，并且易于实现。完整的代码如下：

int FindNumberInArray(int arr[], int n , int find_number)  
{  
  int next_arrive_index = abs(find_number - arr[0]);  
  while (next_arrive_index < n)  
  {  
    if (arr[next_arrive_index] == find_number)  
      return next_arrive_index;  
    next_arrive_index += abs(find_number - arr[next_arrive_index]);  
  }  
  return -1;  
}

转载自：http://blog.csdn.net/morewindows/article/details/10645269