算法の上机实验报告
2020-12-13 14:37
阅读：413
标签：数组 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
cout
return middle;
}
if(x>a[middle]){
left =middle + 1;
}
else {
right = middle -1;
}
}
cout
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
评论
亲，登录后才可以留言！