7-1题目：输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入格式:
输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。
输出格式:
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入样例:
4
1 2 3 4
1
输出样例:
0 2
算法描述
二分搜索算法的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x=a[n/2]，则找到x，算法终止；如果x<a[n/2]，则只在数组a的左半部继续搜索x；如果x>a[n/2]，则只在数组a的右半部继续搜索x。
具体算法
#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;
}
else {
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;
}
算法时间及空间复杂度分析
每执行一次while循环，待搜索数组的大小减小一半。因此在最坏情况狂下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的时间复杂度为O(logn)。
算法空间复杂度为O(1)。
心得体会
此次上机实践我作为理解代码的同学，虽然没有自己打代码，但是通过观看队友打代码和两人讨论，学习了很多，收获了很多。在老师提问时，我成功答不上来。因而发现了自己学习的漏洞：不知道return是什么东西，不理解返回值的意思。课后我已认真学习，弥补
不足。以下链接已经对我的问题作出详细解答。http://www.cnblogs.com/fzhe/archive/2012/12/13/return.html https://blog.csdn.net/ftell/article/details/80106983