【实践报告】算法第二章实践报告

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【实践报告】算法第二章实践报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2251字，纯文字阅读大概需要4分钟。

内容图文

实践报告任选一题进行分析。

 

1.实践题目：

　　7-1 二分查找 

　　输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

　　输入格式:输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。

　　输出格式:输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

 

2.问题描述：

　　输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

 

3.算法描述：

　　首先，我们将n个非降序排列的整数存入数组中，方便后续的操作与比较。然后采用while循环，将要查找的数x与数组中间值进行多次比较，如果和a[n/2]相等则找到，该算法终止。如果x<a[n/2]，则只在数组a的左半部分继续搜索即可，反之就在a数组的右半部分搜索，直至找到该数字，同时用一个变量count记录每一次查找比较的次数用来最后输出。                          

 

4.算法时间及空间复杂度分析：

时间复杂度：每执行一次while循环，被搜索数组的大小缩减为原来的一半，最优情况是一次就找到要查找的数复杂度为O(1)，最坏的情况下复杂度为O(logn)。

空间复杂度：我们采用的二分法算法为非递归算法，其空间复杂度为O(1)

 

5.心得体会（对本次实践收获及疑惑进行总结）：

　　本次结对编程的实践，让我收获了特别多，

在解题过程中，一开始我的审题总是比较大意，没看清楚题目就开始要编程，一开始还以为我们需要先对数据进行排序，然后再进行二分查找。幸好菲凡及时提醒我原本数据就是已经排好序的，才让我免去做无用功的时间，有队友的感觉真好。然后在编程的过程中，菲凡有时会出现一些语法错误，我也能及时帮她指正，我们共同体会到和同伴一起思考一起讨论，然后解决问题的那种成就感，这让我体会到编程不一样的乐趣。另一方面，我也在实践中充分理解与掌握了课本中的算法知识，真正在实践中学习，在实践中明确自己的不足，一点点一点点进步。

 

PS:代码展示

#include<iostream>
using namespace std;
int main(){
　　int n,x;
　　cin>>n;
　　if(1<=n&&n<=1000){
　　int a[n];
　　for(int i=0;i<n;i++) cin>>a[i];
　　cin>>x;
　　int count = 0;
　　int left = 0;
　　int right = n-1;
　　while(left<=right){
　　　　count++;
　　　　int mid = (left+right)/2;
　　　　if (x==a[mid]) {
　　　　　　cout<<mid<<endl<<count;
　　　　　　return 0;
　　　　　　}
　　　　if (x>a[mid]) left=mid + 1;
　　　　　　else right= mid -1;
　　　　　　}
　　　　cout<<"-1"<<endl<<count;
　　　　}
　　　　return 0;
　　　　}

内容总结

以上是互联网集市为您收集整理的【实践报告】算法第二章实践报告全部内容，希望文章能够帮你解决【实践报告】算法第二章实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---