相邻元素差的绝对值都是1,在这样的数组中找目标元素

有这样一个数组A,大小为n,相邻元素差的绝对值都是1。如:A={4,5,6,5,6,7,8,9,10,9}现在,给定A和目标整数t,请找到tA中的位置。除了依次遍历,还有更好的方法么?

这道题目的解法非常有趣。

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

void PrintfArray(int a[], int n)    
{    
  for (int i = 0; i < n; i++)    
      printf("%d ", a[i]);    
  putchar('\n');    
}   
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;  
}  
和这个题目类似的还有这个:

有一个int型数组,每两个相邻的数之间的差值不是1就是-1.现在给定一个数,要求查找这个数在数组中的位置。



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。