算法の上机实验报告

2020-12-13 14:37

阅读：395

标签：数组 lang 代码问题： binary 循环心得体会有序时间

1.题目：

输入n值(1

输入格式:

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

输出格式:

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

输入样例:

4
1 2 3 4
1

输出样例:

0
2

2.问题描述：
用二分查找在一个有序数组中找一个数，并求出比较次数。

3.算法描述：
使用二分查找算法，每进行一次比较判断前计数加一。
  代码如下：

#include

using namespace std;

int BinarySearch(int a[],int x,int n){

int left = 0;

int right =n-1;

int count =0;

while(left

int middle = (left + right)/2;

count++;

if(x== a[middle]){

cout

return middle;

}

if(x>a[middle]){

left =middle + 1;

}

else {

right = middle -1;

　　　}

　　cout

　　return -1;

}

int main(){

　　int n;

　　cin>>n;

　　int *a=new int[n];

　　for(int i=0; i

　　 cin>>a[i];

　　}

　　int x;

　　cin>>x;

　　BinarySearch(a,x,n);

　　return 0;

}

4.算法时间复杂度及空间复杂度
   原本规模为n，运用了二分法，每次都除以二，即o(logN),
   空间复杂度为o（1）。
5.心得体会（对本次实践收获及疑惑进行总结）
 （1.巩固了二分查找法，学会了在二分查找算法里面计数。
（2.也解决了对“在函数里面输出结果然而还要用return”的问题：因为若不用return，
 循环不得停止，则也没办法退出循环输出查找不到的情况。

算法の上机实验报告

标签：数组 lang 代码问题： binary 循环心得体会有序时间

原文地址：https://www.cnblogs.com/twojiayi/p/11566937.html

上一篇：javascript数据类型（四）--- 函数对象之基础

下一篇：python中的lambda函数用法

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

亲，登录后才可以留言！

算法の上机实验报告

输入格式:

输出格式:

输入样例:

输出样例:

评论

热门文章

推荐文章

最新文章

置顶文章