首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2166字,纯文字阅读大概需要4分钟。
内容图文
![算法第二章上机实践报告](/upload/InfoBanner/zyjiaocheng/852/ad0a4a8d364c45be8f08cbf6c4e26870.jpg)
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和比较次数。
输入样例:
4
1 2 3 4
1
输出样例:
0
2
2.问题描述
要求设置一个长度为n的数组,输入数组并对它进行排序,然后利用二分查找某个数值x,查找成功则输出其所在位置及比较次数,否则输出-1及比较次数;另外,n的范围、输入格式及输出格式都有要求:0<=n<=1000;输入共三行: 第一行是n值; 第二行是n个整数; 第三行是x值。;查找成功则输出其所在位置及比较次数,否则输出-1及比较次数。
3.算法描述
假设现有数据是按升序排的,对于给定值x,从序列的中间位置开始比较,如果当前位置的值等于x,则查找成功;若x小于当前的值,则在数列前面的数据中查找;若x大于当前的值则在数列后面的数据中继续查找。
源代码
#include <iostream>
using namespace std;
int BinarySearch(int a[],int x,int n){
int left = 0;
int right =n-1;
int k =0;
while(left <= right){
int middle = (left + right)/2;
k++;
if(x== a[middle]){
cout<<middle<<endl;
cout<<k;
return middle;
}
if(x>a[middle]){
left =middle + 1;
}
else {
right = middle -1;
}
}
cout<<"-1"<<endl;
cout<<k;
return -1;
}
int main(){
int n;
cin>>n;
int *a=new int[n];
for(int i=0; i<n;i++){
cin>>a[i];
}
int x;
cin>>x;
BinarySearch(a,x,n);
return 0;
}
4.算法时间及空间复杂度分析(要有分析过程)
时间复杂度:没进行一次比较,数组长度就变为原来的一半,所以while循环的次数就是时间复杂度。总共有n个元素,比较以后是n, n/2, n/4,....n/2^k,其中k为循环的次数,因n/2^k取整后>=1,故令n/2^k=1得:k=log2n,则有时间复杂度为O(logn)。
空间复杂度:因辅助空间是常数级别的,故空间复杂度是O(1)。
5.心得体会(对本次实践收获及疑惑进行总结)
本次上机其实时间应该是足够的,但是由于我对二分法还不是特别了解,所以拖了很长一段时间也没有完成,算法是写好了,但是因为卡在一个点上所以答案一直错误。明明代码和隔壁组的相差无几,但是别人就是正确自己就是错误。做题的时候跟组内成员讨论无果后,我选择了向其他组同学求教和自己查阅资料。发现其他同学都是很容易就做了出来,这让我认识到,自己的编程能力还得好好努力才能提高。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。