首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2206字,纯文字阅读大概需要4分钟。
内容图文
![算法第二章上机实践报告](/upload/InfoBanner/zyjiaocheng/852/3435f0af050243cdaf95192b89827211.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
2.问题描述
通过改写二分搜索算法,若x在数组中,给出下标,当x不在数组中时,给出小于x的最大元素的下标以及大于x的最小元素的下标
3.算法描述
在二分搜索算法的基础之上,如果x在数组中,输出x在数组中对应的下标两次;如果x不在数组中,最终right的值就是小于x的最大元素的下标,最终left的值就是大于x的最小元素的下标。
#include<iostream>
using namespace std;
int middle;
int bs(int a[],int x,int n)
{
int left = 0;int right = n-1;
while(left<=right){
middle = (left+right)/2;
if(x == a[middle]) cout<<middle<<' '<<middle;
if(x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return right;
}
int main()
{
int n = 1000;
cin>>n;
int a[n];
int x;
cin>>x;
for(int i = 0;i<n;i++)
cin>>a[i];
int j = bs(a,x,n);
if(x != a[middle]) cout<<j<<' '<<j+1;
return 0;
}
4.算法时间及空间复杂度分析(要有分析过程)
算法在最坏的情况下while循环体会被执行O(log n)次,执行一次循环体需要O(1)时间,所以在最坏的情况下,时间复杂度为O(log n)。需要的辅助存储空间就是left, right, middle对应的存储空间,所以该算法的空间复杂度为O(1)。
5.心得体会(对本次实践收获及疑惑进行总结)
刚开始一直没有找到规律以为会分多种情况,后来才发现原来最后right和left的值就是要找到的下标值。当x就在数组中时,要输出两次下标值,否则在pta上会部分错误。通过这道题目,对二分搜索中while循环的步骤更清楚了,因为在找到规律的过程中要一次次在纸上执行while循环,确定right, left, middle的变化。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。