算法第二章上机实践报告

2020-12-13 14:47

阅读：466

标签：else microsoft style font soft for 中心分析 size

1.实践题目

7-1 二分查找

2.问题描述

输入n值(1

输入格式:

输入共三行：第一行是n值；第二行是n个整数；第三行是x值。

输出格式:

输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入样例:

4
1 2 3 4
1

输出样例:

0
2


3.算法描述

核心算法是二分查找，将已经排好的序列一分为二，划分的中心数定义为mid，然后将mid与要查找的数相比较，根据大小再将将其划分。

源代码：

#include

using namespace std;

int s(int a[], int x, int n)

{

int l=0, r=n-1, num=1;

int mid;

int p=0;

while(l

{

mid=(l+r)/2;

if(x==a[mid])

{

p=1;

cout

break;

}

else if(x>a[mid])

{

l=mid+1;

num++;

}

else

{

r=mid-1;

num++;

}

if(p==0)

{

cout

}

int main()

{

int n,i,x;

int a[1000];

cin>>n;

for(i=0;i

{

cin>>a[i];

}

cin>>x;

s(a,x,n);

return 0;

}

4.算法时间及空间复杂度分析

时间复杂度实际上就是while循环的次数，总共有n个元素，渐渐跟下去就是n,n/2,n/4,....n/2^k（k为循环次数），令n/2^k=1，可得k=log2n,则时间复杂度为O(n)=O(log2n）（以2为底，n的对数）。

5.心得体会

在大一学习c++的时候就已经初步了解过这种方法，现在对这种方法的使用可以说更加流畅。在使用中尤其要注意再次划分时的mid+1和mid-1，以免出错。

算法第二章上机实践报告

标签：else microsoft style font soft for 中心分析 size

原文地址：https://www.cnblogs.com/lisihao/p/11569187.html

上一篇：ASP.NET MVC 伪静态的实现

下一篇：关于WPF的验证

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法第二章上机实践报告
文章链接：http://soscw.com/essay/34478.html

亲，登录后才可以留言！

算法第二章上机实践报告

输入格式:

输出格式:

输入样例:

输出样例:

评论

热门文章

推荐文章

最新文章

置顶文章