白话经典算法系列之十五 “一步千里”之数组找数

迈不过友情╰ 2023-06-18 07:57 63阅读 0赞

首先看看题目要求（题目来源：[http://weibo.com/lirenchen][http_weibo.com_lirenchen]，特此鸣谢）：

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

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

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

// 【白话经典算法系列之十五】“一步千里”之数组找数
    //  by MoreWindows( http://blog.csdn.net/MoreWindows ) 
    //  欢迎关注http://weibo.com/morewindows
    #include <stdio.h>
    #include <math.h>
    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 main()
    {
      printf("    【白话经典算法系列之十五】“一步千里”之数组找数\n");
      printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n");
      printf(" -- http://blog.csdn.net/morewindows/article/details/10645269 -- \n\n");
     
      const int MAXN = 10;
      int arr[MAXN] = {4,5,6,5,6,7,8,9,10,9};
      PrintfArray(arr, MAXN);
      for (int i = 0; i < MAXN; i++)
        printf("查找%d   \t下标为%d\n", arr[i], FindNumberInArray(arr, MAXN, arr[i]));
     
      printf("查找%d   \t下标为%d\n", -1, FindNumberInArray(arr, MAXN, -1));
      printf("查找%d   \t下标为%d\n", 0, FindNumberInArray(arr, MAXN, 0));
      printf("查找%d   \t下标为%d\n", 100, FindNumberInArray(arr, MAXN, 100));
      return 0;
    }

运行结果如下图所示：

![SouthEast][]

[http_weibo.com_lirenchen]: http://weibo.com/lirenchen
[SouthEast]: https://img-blog.csdn.net/20130831110459187?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTW9yZVdpbmRvd3M=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast