【数据结构】查找算法：二分查找、顺序查找
08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.csdn.net/xiaowei_cqu/article/details/7747205
查找算法
【结果分析】
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
