针对PTA上算法第二章实践中的第二题进行分析
实践题目:
算法第二章上机实践报告
问题描述:
设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相 同,均为x在数组中的位置。

算法分析:
#include<iostream>
using namespace std;
void find(int a[],int x,int n) //定义一个函数,通过二分查找判断x位于数组中的哪个位置或者应插入数组的哪个位置
{
int l=0;int r=n-1;
while(l<=r)
{
int mid=(l+r)/2;
if(x==a[mid])
{
cout<<mid<<" "<<mid;
return;
}
else if(x>a[mid])
{
l=mid+1;
}
else
{
r=mid-1;
}
}
if(x<a[l]) cout<<l-1<<" "<<l;//以a[l]为界,如果x在a[l]左边,那么输出l以及l+1
if(x>a[l]) cout<<l<<" "<<l+1;//如果x在a[l]左边,那么输出l-1以及l
return;
}
int main()
{
int n,x,p;
int a[100001];
cin>>n;
cin>>x;
for(int i=0;i<n;i++)
cin>>a[i];
if(x<a[0])//若x小于全部数值
{
cout<<-1<<" "<<0;
}
else if(x>a[n-1])//若x大于全部数值
{
cout<<n-1<<" "<<n;
}
else//
find(a,x,n);
return 0;
}
算法时间及空间复杂度分析:
该算法的时间复杂度为O(log2 n)
空间复杂度为O(1)
心得体会:
原先老师还没要求时间复杂度为O(log2 n)时,我是直接在main函数里直接写了if进行判断的,然后一堆的判断语句。把时间复杂度扩大到了O(n)。后来就开始思索要怎样将复杂度变小。最后就反思自己的代码,思考如何在二分查找的find函数里进行大小判断,这样就可以将时间复杂度变为O(log2 n)。后来就是在二分查找后,加上了下面这两个语句。
if(x<a[l]) cout<<l-1<<" "<<l;//以a[l]为界,如果x在a[l]左边,那么输出l以及l+1
if(x>a[l]) cout<<l<<" "<<l+1;//如果x在a[l]左边,那么输出l-1以及l
我觉得我们在做题的时候,不能只是将题目完成了就好,要好好思考怎么将代码变得简洁及时间、空间复杂度降到最优,这也是算法课存在的意义。打题还是要多思考,多严格要求自己,不能想着投机取巧,单纯完成题目就好。
然后对上机打题的体验感很好,可以和组员一起思考,一起讨论,共同完成题目的感觉挺好的。
算法第二章上机实践报告
原文:https://www.cnblogs.com/wen-05/p/11569983.html