【数据结构】查找算法：二分查找、顺序查找

08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205

查找算法

查找算法是在存在的序列（list） 中查找特定的目标（target），要求序列中每个记录必须与一个关键词（key）关联才能进行查找。
查找算法通常需要两个输入：1、被查找的序列2、要查找的关键词查找算法的输出参数和返回值：1、返回类型为 Error_code 的值用以表示是否查找成功2、如果查找成功，返回 success， 输出参数 position 定位到目标所在位置3、如果查找失败，返回 not present，输出参数可能是未定义或不同于已有位置的任何值
顺序查找算法
顺序查找算法的思路很简单：从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。

【实验说明】题目：编写一个程序，对顺序表{3,6,2,10,1,8,5,7,4,9},采用顺序查找关键字5的过程。要求输出：
1）原顺序表；2）查找到关键字的位置；3）进行比较的次数。
1.首先要编写类表List。需要满足最基本的操作插入insert（），获取retrieve（），以及得到大小size（）。
2.我们观察题目要求，表中虽然存储的是简单的整数，但如果我们使用List<int>对象显然无法记录比较次数，所以我们自己写一个类Key通过其内部int类型的数据成员来记录存于表中的值，并模仿int基本的逻辑操作，即编写重载逻辑运算符，同时增加一个静态数据成员comparisons用于记录其比较操作的次数。
3.准备工作做好之后开始编写顺序查找算法。算法的思路很简单，也较易实现，从表中第一个元素开始比较，发现目标则返回元素所在表中位置；若遍历之后没有目标，则查找失败，返回-1表示表中没有目标元素。4.按题目要求编写最后的输出函数。
【相关代码】函数 sequential_search

【结果分析】
A.实现顺序查找算法1.顺序查找算法思路很简单，就是一种遍历的思想，一个个查找目标元素，实现也很简单。
2.对于有n个元素的表适用顺序查找。比较次数：不成功：比较n次。成功查找：最好的情况为1次，即第一个元素即为目标元素；最差的情况为n次；平均比较次数（n+1）/2次。
所以当表很大时，顺序查找的代价是很大的。
3.顺序查找算法不会有重复的比较出现，即一旦找到即成功，但同时这种代价是当表中有重复的目标元素时（比如有多个目标元素）我们只能得到第一个元素的位置。
B.实现二分查找算法1.二分查找法思路：递增排列的表，首先从中间元素开始查找，如果元素比目标元素小，则查找后半部分表，反之查找前半部分表，并重复这一过程。这样每次查找中我们都把表的长度减半。
2.二分查找在实现中有量bottom和top，每次减半的过程体现在bottom和top的改变上，在代码的实现上可以使用单纯的循环或者用函数递归的思想。
递归思想更容易理解，但编写之后我们发现函数是尾递归，尾递归通常可以用简单的循环实现，循环在操作来说没有了函数调用的过程，更节省时间和空间。
3.编码中小小地方的改动可能对程序有很大的改观。
如上述两种二分查找binary_search_1（不比较等于的情况）binary_search_2（添加等于情况）


转载请注明出处：http://blog.csdn.net/xiaowei_cqu/article/details/7748260
实验代码下载：http://download.csdn.net/detail/xiaowei_cqu/4437702

7楼lullcc10小时前
学习学习
Re: xiaowei_cqu9小时前
回复lullcc有问题欢迎指正~
6楼lishehe昨天 17:31
学习……
Re: xiaowei_cqu10小时前
回复lishehe :-)
5楼livemylife前天 19:26
二分的精髓不是在有序表中找到某个目标。n而是能够在固定的时间内抛弃数据列表的一半数据从而达到log(n)的时间复杂度，而这个列表可以是有序的也可以是无序的。
Re: xiaowei_cqu前天 19:51
回复livemylife无序怎么抛弃一半？
Re: livemylife昨天 20:38
回复xiaowei_cqun这里给你一道题吧。n在一个无序没有重复数字的数组中查找局部最小值，如果数组中存在多个局部最小值，返回任意一个最小值的index就可以。n局部最小值的定义是该数字比他的左右邻居都小。如果该数字是数组的边缘，则只需要对比与他相邻的一个数字。如果只有1个数字，则这个数字是他自己。nO(n)大家都能搞定的，你尝试一下用Log(n)来解决喽。
Re: xiaoyukid昨天 16:16
回复livemylifenmark..
4楼zsw12013前天 19:03
刚才看你写的在大学期间的课程列表，我的大学啥都没怎么学到，现在女的都怎么厉害了，这叫我们这些爷们情何以堪啊，估计这以后的日子不好混啊
3楼lbq613613前天 18:48
基础往往决定一个人能达到的高度！lz加油！
2楼xmlovedm3天前 12:13
学习学习，希望和楼主交个朋友
Re: xiaowei_cqu3天前 12:38
回复xmlovedm我关注你了~
1楼liutengteng1303天前 11:49
学习了，加油。
Re: xiaowei_cqu3天前 11:57
回复liutengteng130谢谢鼓励  ^_^