《算法设计与分析》--算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法设计与分析》--算法第二章上机实践报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2491字，纯文字阅读大概需要4分钟。
内容图文
开门见山，直接上题目。
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
题目分析
为什么要选择这道题来讲呢？那就是因为我太菜了，理解不了第三题的时间复杂度O（logn）的算法，只好拿这道题讲一下了。
好了，这里讲一下我的思路吧。
首先，需要理清题意，题目说的是返回下标，而不是位置，所以数组里的数组最好从下标0开始，这样子到后面的时候就不会弄的很乱；
我们在进一步分析一下，返回下标--如果找到了需要寻找的数，那么就返回两个相同的下标即找到目标数字的下标。那么没找到的情况呢？题目也很明显给了两个提示了，就是返回一个它邻边的两个数，如下：
但是还有一个问题，那就是边界问题。题目已经给出提示了，这里就不重复赘诉了。
理清思路之后，我开始构思算法了，很明显，这是一个典型的二分算法，毕竟题目已经是一个很明显的提示了。
那么基于二分算法，如果找到目标数字就返回改数字所在下标，若果没有找到就返回“l”下标；该函数如下：
int find(int* a, int l, int r,int goal){
while(l <= r){
int mid = (l + r) >> 1;
if(a[mid] == goal){
return mid;
}
else if(a[mid] < goal){
l = mid + 1;
}
else {
r = mid - 1;
}
}
return l; //返回“l”下标，即为找不到目标数字时的右邻边下标；
}
对于没找到目标函数的情况，只需要对上面find函数的返回值输出一个“l - 1” 和 “l”；
搞定这个函数之后剩下的事情就简单很多啦，主函数只要判断一下有无找到目标函数，然后分情况输出就ok。
下面是AC代码：
#include <iostream>
using namespace std;
int find(int* a, int l, int r,int goal){
while(l <= r){
int mid = (l + r) >> 1;
if(a[mid] == goal){
return mid;
}
else if(a[mid] < x){
l = mid + 1;
}
else {
r = mid - 1;
}
}
return l;
}
int main ()
{
int n, x, a[100005];
cin >> n;
cin >> x;
for(int i = 0; i < n; i++)
cin >> a[i];
int f = find(a, 0, n-1, x);
if(a[f] == x) cout << f << " " << f;
else cout << f - 1 << " " << f;
return 0;
}
改写二分算法
算法分析：
时间复杂度：数组长度为n，因为对数组进行了二分查找，问题规模是n，所以时间复杂度为O（logn）；
空间复杂度：只开了几个变量，所以空间复杂度为O（1）；
心得体会：
打代码我觉得最重要的还是理清自己的思路吧，有一个好的构思才能做出好的算法；还有注意细节；
我觉得我好菜；遇到难题半途..哦不，是知难而退。
Bye--bye~
内容总结
以上是互联网集市为您收集整理的《算法设计与分析》--算法第二章上机实践报告全部内容，希望文章能够帮你解决《算法设计与分析》--算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。