首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1678字,纯文字阅读大概需要3分钟。
内容图文
![算法第二章上机实践报告](/upload/InfoBanner/zyjiaocheng/852/b445d5796a974715b09441eaa9c45010.jpg)
1、实践题目
输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
2、问题描述
利用二分法在一个有序的序列中查找一个已知数,若查到,输出该数的下标和比较次数,若查不到,输出-1和比较次数。
3、算法描述
这题主要有两个点,一是二分算法的实现,二是实现比较次数的统计。
比较次数用了一个全局变量count,每次调用算法binarySearch则加1,实现了比较次数的统计。
二分算法用了递归,先判断左右边界是否相等,左右边界相等且不等于x,说明没有找到目标数,输出-1和比较次数,左右边界不等,判断序列最中间的数和x的关系,若相等直接返回,若不相等进一步判断并进行递归。
算法完整代码如下:
#include<iostream> using namespace std; int count=0; int binarySearch(int a[],int left, int right, int x){ count++; if(left==right&&a[left]!=x){ return -1; } else{ int mid = (left+right)/2; if(a[mid]==x){ return mid; } if(x>mid){ return binarySearch(a,mid+1,right,x); } else{ return binarySearch(a,left,mid-1,x); } } } int a[1005]; int main(){ int x,n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } cin>>x; int ans; ans = binarySearch(a,0,n-1,x); cout<<ans<<endl<<count;
4、算法时间及空间复杂度分析
二分搜索每次搜索都排除一半的数值
每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。
每次取整总有n/2^k>=1 最坏情况时n/2^k=1
解出来得算法时间复杂度为O(log2(n))。
由于是辅助空间所以空间复杂度为O(1)。
5、心得体会
这次的实践是结对合作完成,一开始也出现了一些问题,比如算法中二分了之后的边界问题,我一开始设置的是left—mid,这样mid就多参与了一次递归,导致结果出现偏差,在这次的实践里面,让我对二分搜索的理解更加深刻,不再是当时听理论时模糊的概念,而是有一个清晰的思路在脑中,之前的对二分搜索的困惑也得到了很好的解决。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。