首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2476字,纯文字阅读大概需要4分钟。
内容图文
![算法第二章上机实践报告](/upload/InfoBanner/zyjiaocheng/852/c470588c4488430f8a09dc7e80d4e126.jpg)
1.实践题目
7-2 改写二分搜索算法 (20 分)
题目来源:《计算机算法设计与分析》,王晓东
设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。
输入格式:
输入有两行:
第一行是n值和x值; 第二行是n个不相同的整数组成的非降序序列,每个整数之间以空格分隔。
输出格式:
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时,i和j相同。 提示:若x小于全部数值,则输出:-1 0 若x大于全部数值,则输出:n-1的值 n的值
输入样例:
在这里给出一组输入。例如:
6 5
2 4 6 8 10 12
输出样例:
在这里给出相应的输出。例如:
1 2
#include <iostream>2.问题描述
问题是让我们改写二分搜索法,在一个有序的序列中查找一个已知数,当这个数在数组中时,返回小于这个数的最大元素的位置和大于这个数的最小元素的位置。当这个数小于这个序列的第一个数,返回-1和0.当这个数大于序列最后一个数
返回数组中最后一个元素的位置和值。
3.算法描述
先设置了一个全局变量(用来辅助输出)
函数BinarySearch:
设置两个变量left和right
判断要找的那个数是否在这个数组范围内,
如果小于第一个数 返回-1
如果大于最后一个数 返回 n(这个n是序列的个数,后来也是用来辅助输出的)
如果在数组内:
?? 设置一个循环(界限为left<=right)
?? 设一个变量 m = (left+right)/2
?? 如果找到要找的数,将num=m,返回m
如果没找到 返回right(因为推出循环,left肯定是大于right,意味着当left=right时,这个数大于在这个位置的数,所以返回right(这个位置的数是小于这个数的最大数))
算法完整代码如下:
using namespace std; int num=-2;
int BinarySearch(int a[],int t,int n)
{
?int left = 0;
?int right = n-1;
?if(t<a[left]) return -1;
?else if(t>a[right]) return n;
?else{
??while (left<=right){
?? int m = (left+right)/2;
?? if(t==a[m]) {
?? ?num = m;
?? ?return m;}
?? if(t>a[m]) left = m+1;
?? else right = m-1;
?}
?return right;
?}
} int main(){
?int a,d;
?cin>>a>>d;
?int b[1000];
?for(int c=0;c<a;c++){
??cin>>b[c];
?}
?int e;
?e=BinarySearch(b,d,a);
??? if(e==-1) cout<<e<<" "<<0;
??? else if(e==a) cout<<a-1<<" "<<b[a-1];
??? else if(num==e) cout<<e<<" "<<e;
??? else cout<<e<<" "<<e+1;
?return 0;
} ? ? 4.算法时间和空间复杂度分析 总共有n个元素。
第1次折半:还剩n/2个元素
第2次折半:还剩n/4个元素
第3次折半:还剩n/8个元素
……
第k次折半:还剩n/2^k个元素
最坏的情况下,最后还剩1个元素,令n/2^k = 1。得k=logn。
时间复杂度O(logn)
由于辅助空间是常数级别的所以:
空间复杂度是O(1); ? 5.心得体会 这个道的思路是比较简单的,唯一比较难的是返回那个right的时候想了挺久的。通过这次结对编程,共同体会到和同伴一起思考一起讨论,然后解决问题的那种很好的感觉。也通过实践,加深了对课本知识的理解。 ??
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。