经典算法（15） “一步千里”之数组找数

经典算法（15） “一步千里”之数组找数2014-01-03 csdn 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.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（"
"）;} 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（"【白话经典算法系列之十五】“一步千里”之数组找数
"）;printf（" -- by MoreWindows（ http://blog.csdn.net/MoreWindows ） --
"）;printf（" -- http://blog.csdn.net/morewindows/article/details/10645269 -- 

"）; 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 	下标为%d
", arr[i], FindNumberInArray（arr, MAXN, arr[i]））; printf（"查找%d 	下标为%d
", -1, FindNumberInArray（arr, MAXN, -1））;printf（"查找%d 	下标为%d
", 0, FindNumberInArray（arr, MAXN, 0））;printf（"查找%d 	下标为%d
", 100, FindNumberInArray（arr, MAXN, 100））;return 0;}

运行结果如下图所示：

本文地址：http://blog.csdn.net/morewindows/article/details/10645269