一、实践题目
二分查找
二、问题描述
输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入格式:
输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。
输出格式:
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
三、算法描述
本题考验的知识主要分为逻辑理论和操作实践。理论上考验的是对二分查找问题中思想的理解；操作中考验的是将解题步骤转化为代码实现的能力。
从逻辑理论来说，将一个大问题划分为若干个类似的小问题，是二分查找的主要思路；从编程来看，我们在代码实现中运用的是数组和循环体的知识。
以下为具体代码：
#include <iostream>
using namespace std;
int BinarySearch(int a[],int x,int n){
int left = 0;
int right = n-1;
int k = 0;
while (left <= right){
int middle = (left + right)/2;
k++;
if(x==a[middle]){
cout<<middle<<endl;
cout<<k;
return middle;
}
if(x > a[middle]){
left = middle +1;
}
if(x < a[middle]){
right= middle -1;
}
}
cout<< "-1"<<endl;
cout<<k;
return -1;
}
int main(){
int n;
cin>> n;
int *a= new int[n];
for(int i=0;i<n; i++){
cin>>a[i];
}
int x;
cin>> x;
BinarySearch(a,x,n);
return 0;
}
四、算法时间及空间复杂度分析
最坏情况下时间复杂度为O(logn),因为每一次循环都是把问题规模减半，故要找到指定数字，则计算以问题规模n为对数的值即为循环次数。
空间复杂度为O(1)，因为空间复杂度是计算算法的辅助空间单元的个数，即为算法执行时创建的变量个数，此算法创造的辅助变量为常数，故空间复杂度为常数。
五、心得体会
本次上机实践中，遇到问题例如数组的使用、循环体的逻辑关系，代码的使用语法等时，翻阅参考书中资料做出代码实现；同时作为负责编程的同学，我与结对编程伙伴对所编写的程序进行讨论交流，实在不清楚的地方一起使用互联网的力量查找信息。在这整个过程中，我认为自己收获颇多。
算法第二章上机实践报告
原文：https://www.cnblogs.com/nanvoqnlo/p/11573913.html
