7-1 二分查找 （20 分）

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入格式:

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

输出格式:

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

输入样例:

41 2 3 41

输出样例：

 0

    2

代码描述

#include<iostream>

using namespace std;

int count=0;

int binarySearch(int a[],int left, int right, int x){

count++;

if(left==right&&a[left]!=x){

return -1;

}

else{

int mid = (left+right)/2;

if(a[mid]==x){

return mid;

}

if(x>mid){

return binarySearch(a,mid+1,right,x);

}

else{

return binarySearch(a,left,mid-1,x);

}

}

}

int a[1005];

int main(){

int x,n;

cin>>n;

for(int i=0;i<n;i++){

cin>>a[i];

}

cin>>x;

int ans;

ans = binarySearch(a,0,n-1,x);

cout<<ans<<endl<<count;

return 0;

}

算法时间空间复杂度分析：

因为二分查找每次排除一半的值，最好的情况是排除一次就得到结果，最坏的情况是排除到只剩一个值才得到结果，所以其时间复杂度为log2（n），空间复杂度为O（1）。

心得体会：

实践前虽然大概了解二分搜索的思路，但却只是停留在把一组有序数列一次次缩半而已，而这次实践让我对二分搜索的细节了解的更加清晰，如在编写代码过程中，在缩半前要先比较大小，接着还要改下标，本次实践让我将二分搜索的思路写出代码，了解其更多细节，而不仅仅是停留在大概了解上。