【土语经典算法系列之十五】“一步千里”之数组找数

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

本文地址：http://blog.****.net/morewindows/article/details/10645269转载请标明出处，谢谢。

欢迎关注微博：http://weibo.com/MoreWindows

首先看看题目要求（题目来源：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.****.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.****.net/MoreWindows ) --\n");
  printf(" -- http://blog.****.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;
}

运行结果如下图所示：

【土语经典算法系列之十五】“一步千里”之数组找数

本文地址：http://blog.****.net/morewindows/article/details/10645269转载请标明出处，谢谢。

欢迎关注微博：http://weibo.com/MoreWindows

6楼miao66646592小时前: 直接二分搜索也行，但是返回的下标有可能不是第一个出现位置的下标。nint binarySearch(int a[],int key,int N)n{ntint left=0;ntint right=N-1;ntwhile(left<=right)nt{nttint mid=left+(right-left)/2;nttif(a[mid]<key)ntt{ntttleft=mid+1;ntt}nttelse if(a[mid]>key)ntttright=mid-1;nttelsentttreturn mid;nt}ntreturn -1;n}nint _tmain(int argc, _TCHAR* argv[])n{ntint key;ntint a[]={4,5,6,5,6,7,8,9,10,9};ntwhile(cin>>key)nt{nttcout<<binarySearch(a,key,sizeof(a)/sizeof(int));nttcout<<endl;nt}ntreturn 0;n}

5楼u0119637473小时前: 看不懂

4楼chengzhu_014小时前: 学习

3楼oliveevilo4小时前: 如果数组是一个公差为-1的等差数列“由于每个相邻的数字之差的绝对值为1。故第t个位置之前的数肯定都比y小”这句就不对了吧，比如10,9,8,7,6,5,4,3,2,1，y=1，那么t=9，这样的话第9个数之前的数都比1大，算法貌似没什么问题，只是表述不够准确

2楼mynote4小时前: 代码写得真不错。

1楼chengye_xin昨天 19:02: 思路很有创新。

【土语经典算法系列之十五】“一步千里”之数组找数

相关推荐