资源描述：
《二分搜索实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划二分搜索实验报告 重庆交通大学学生实验报告 实验课程名称算法设计与分析开课实验室数学实验室 学院数学与统计学院年级13专业班信息与计算科学2学生姓名辜朕圆学号3开课时间XX至XX学年第1学期 XX-XX学年第一学期 实验报告题目实验一递归与分治策略 开课实验室：数学实验室指导老师：韩逢庆时间：学院：理学院专业：信息与计算科学班级：XX级2班 姓名：辜朕圆学号：3 一、实验目的 1．加深学生对分治法算法设计方法的基本思想
2、、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。二、实验内容 题目①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 ②写出三分搜索法的程序。三、实验要求目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安
3、保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划 用分治法求解…问题； 再选择自己熟悉的其它方法求解本问题；上机实现所设计的所有算法；四、实验过程设计 1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找算法。如果搜索元素在数组中，则直接返回下表即可；否则比较 XX-XX学年第一学期 搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中
4、继续搜索x。如果x>a[san2]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。五、实验结果分析 (1)例子为数组a[1,2,3,4,5,6,7,8,9],n=9,x=9。 实验结果为 (2)例子为数组a[1,2,3,4,5],x=3,n=5。 实验结果为 时间复杂性：最好情况下，最坏情况下 二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(logn)。三分搜索法：O空间复杂性分析：O。目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升
5、其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划 六、实验体会 本次试验解决了二分查找和三分查找的问题，加深了对分治法的 XX-XX学年第一学期 理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。七、附录： (1)publicstaticintbinarySearch(inta[],
6、intx,intn) { intleft=0;intright=n-1;inti,j;while(lefta[middle])left=middle+1;elseright=middle-1;} i=right;j=left;return0;} 1;} (2) publicclasssanfen{ publicstaticintsanSearch(int[]a,intx,intn){ intleft=0;intright=n-1;while(right>left){ if(xa[right]) {("根本不在数组里");bre
7、ak;}目的-通过该培训员工可对保安行业有初步了解，并感受到安保行业的发展的巨大潜力，可提升其的专业水平，并确保其在这个行业的安全感。为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划 intsan1=(left+right)/3;intsan2=2*(left+right)/3;if(x==a[san1]) { ("找到了");returnsan1;} elseif(xa[san2])left=san1+1; XX-XX学年第一学期 else{left=san1;righ
8、t=fan2;}}} } publicstaticvoidmain(String[]args){} sanfens=newsanf
