鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c语言 > >

2013年2月28日

来源:互联网 作者:佚名 时间:2013-03-05 15:08
无限式查找-----2013年2月28日 问题描述:已知一个数组x[],元素个数有多少并不很清楚,但是数组元素已经依顺序从小大大排好,而且在数组最后添加了足够多的MAX记号;MAX表示最大的值,比数组中每一个元素都大,而且个数足够多。编写一个程序,在这个数组中找

无限式查找-----2013年2月28日

       问题描述:已知一个数组x[],元素个数有多少并不很清楚,但是数组元素已经依顺序从小大大排好,服务器空间,而且在数组最后添加了足够多的MAX记号;MAX表示最大的值,比数组中每一个元素都大,香港空间,而且个数足够多。编写一个程序,在这个数组中找出某个给定的值。

      思路:二分查找法是一个非常高效的算法,但要想使用二分查找法,美国空间,必须满足2个条件:1.元素是有序的,可以从小到大排列,也可以从大到小排列。2.知道元素集合的上界和下界。本题中元素已经从小到大排列,但是不知道数组的上界。所以,解法如下:

      1.最开始,二分查找x[0]和x[1],即查找区域为[0,1)这个左闭右开区间,区间的大小是

。此时start=0,end=1。这是认为构造的一个适合二分查找法的区间。

      2.如果在之前没有查找到,把start=end,end+=

。此时的区间大小是

。再进行二分查找。如果还没找到,继续增大区间到

,直到找到或到达最大值MAX。

      代码很简单,在此就不赘述了。

      参考资料:《C语言精选名题百则技巧篇》

      如果你觉得我的文章对你有帮助,请推荐一下,非常感谢!

posted on

Copyright ©2013 NeilHappy Powered by: 博客园 模板提供:沪江博客

网友评论
<