无限式查找

发布时间:2016-12-7 20:33:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"无限式查找",主要涉及到无限式查找方面的内容,对于无限式查找感兴趣的同学可以参考一下。

本文原文地址:http://dsqiu.iteye.com/blog/1715280 题目: 已知一个数组,元素个数有多少并不很清楚,但是数组元素已经依顺序从小到大排好, 而且在数组最后添加了足够多的记号;表示最大的值,比数组中每一个元素都大,而且个数足够多。编写一个程序,在这个数组中找出某个给定的值。 说明: 因为并不知道数组中有多少个元素,所以虽然数组中元素已经依顺序排列好,也不能套用二分查找法(Binary Search)。不过,二分查找法仍然是最有效率的、在已排好顺序的数组中查找数据的方法。请问,有没有办法克服有关不知道有多少元素的限制呢? 还有一点很重要,很可能不知道那个∞的值究竟是多少;惟一可以确定的就是∞比每一个数组中的值都大,不一定是该类型的最大值。例如,如果数组中的元素是int类型,它 可能是1,3,5,7,9,50,50,50,…,于是50在此就具有∞的作用。 提示:二分法还是可以用的,不过关键是要如何运用它,为了方便起见,假设∞正是该类 型最大的值。 解答: 在使用二分查找的技巧时,要有左边的边界到右边的边界。当然,如果输入值是放在数组中,左边的边界是0,但右边就不知道了。不过因为数组在最后是放了一连串所以很多人就想到一个方法,从头查到尾,想要找出∞这个值。但这很危险:第一,不知道的的真正的值为何,只知道它比数组中其他数都大,所以没有办法确定如的位置;第二,纵使有办法认出∞,比如它在第k个位置,因而就对0与k这一段数据进行二分查找,但是这可能会浪费时间,因为数组中不是∞的元素可能十分多。 在此提供一个做法,它并非是最好的,但效率却与二分查找法相当。第一步是找出一个合理的、距离不太长的范围给二分查找法使用。想法是这样的,先看给定的值GIVEN是 否是x[0],如果不是,就去查x[1]与x[2],如果不在这个范围中,则查x[3]〜x[6],若还不 在,再查x[7]〜x[14]…。换句话说,永远在[start,end)这个区间中查有没有GIVEN,因为 x[]是排好的,这相当于x [start] <= GIVEN && GIVEN < xtend]。如果不在,就把范围推到end开始的区域。这些区域的长度自1 = 2G起,长度分别为2、 2^2、2^3、2^4等,所以查找的范围愈来愈大。在程序中,bound()函数就做这样的工作,用delta表示区间中元素的个数,start是左边起点,而end则是终点的下一个,所以用的区间 是[start,end),而不是[start,end]。很自然地,如果start已知,end就是start+delta。在一开始时,start是0, delta是1,因此范围是[0,1)。接下来,delta要加倍,因此自己相加,再 把start移到end的位置,这就是下一个区间了。可以一再重复,直到[start,end)中包含了GIVEN为止。因为∞比所有的数都大,所以这一定可以做得到,除非GIVEN比∞还大, 但这样就没有意义了。 问题实现: #define NOT_FOUND -1 /* ------------------------------------------------------ */ /* function prototypes */ /* ------------------------------------------------------ */ void bound(int [], int, int *, int *); int search(int [], int, int, int); /* ------------------------------------------------------ */ /* FUNCTION inf_search : */ /* The control routine. */ /* ------------------------------------------------------ */ int inf_search(int x[], int GIVEN) { int left, right; bound(x, GIVEN, &left, &right); /* dound */ return search(x, GIVEN, left, right); /* then search*/ } /* ------------------------------------------------------ */ /* FUNCTION bound : */ /* Given a sorted infinite array and a key GIVEN, this */ /* function returns two subscripts, namely start and end, */ /* which bound the given key. */ /* ------------------------------------------------------ */ void bound(int x[], int GIVEN, int *start, int *end) { int delta = 1; /* interval length */ *start = 0; /* starting from the 1st pos*/ *end = *start + delta; /* interval ends before *end*/ while (!(x[*start] <= GIVEN && GIVEN < x[*end])) { delta += delta; /* if [start,end) can not */ *start = *end; /* bound, then double length*/ *end = *start+delta; /* and try again. */ } (*end)--; /* returns the true bound */ } /* ------------------------------------------------------ */ /* FUNCTION search : */ /* The traditional binary search function. */ /* ------------------------------------------------------ */ int search(int x[], int GIVEN, int low, int high) { int mid; while (low <= high) { mid = (low + high)/2; if (GIVEN < x[mid]) high = mid - 1; else if (GIVEN > x[mid]) low = mid + 1; else return mid; } return NOT_FOUND; } /* ------------------------------------------------------ */ #include <stdio.h> #include <stdlib.h> /* for atoi() */ #include <limits.h> /* for INT_MAX */ void main(void) { int number[30] = { 1, 3, 5, 8, 10, 21, 25, 50, 67, 68, 70, 84, 100, 130, 150, 151, 170, 180, 200, 300, 459, 480, 499, 503, 555, 570, 623, 699, 784, 981}; int input[100]; int i, key, answer; char line[100]; for (i = 0; i < 30; i++) input[i] = number[i]; for (i = 30; i < 100; i++) input[i] = INT_MAX; printf("\nInfinite Search Program"); printf("\n======================="); printf("\n\nGiven Infinite Sorted Array :"); for (i = 0; i < 100; i++) { if (i % 15 == 0) printf("\n"); if (input[i] < INT_MAX) printf("%4d", input[i]); else printf(" inf"); } printf("\n\nYour Search Key Please --> "); gets(line); key = atoi(line); if ((answer = inf_search(input, key)) >= 0) printf("\nKey found at position %d", answer); else printf("\nKey NOT FOUND!"); }

上一篇:Java数组使用技巧
下一篇:通向架构师的道路(第十五天)IBM Websphere的安装与优化

相关文章

关键词: 无限式查找

相关评论