1 实践题目

2 问题描述

输入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

输出样例:

02 要求设置一个长度为n的数组，输入数组并进行排序，然后利用二分查数值x，查找成功后输出其所在位置及比较次数，否则输出-1及比较次数；

另外，n的范围、输入格式及输出格式都有要求：0<=n<=1000；输入共三行： 第一行是n值； 第二行是n个整数；

第三行是x值。查找成功则输出其所在位置及比较次数，否则输出-1及比较次数。 3.算法描述：首先，二分查找在查找前先用left和right指针表示数组第一和最后一个数，接着用middle代表数组中间的数，（left+right）/2这一地址值赋给middle。 然后将要查找的目标数与middle对应值的比较，若目标数比middle对应值大，说明目标数在middle到n-1的区间里，此时把middle值赋给left， 同理，当目标数比middle对应值小，则说明在0到middle区间，此时把middle值赋给right，依此循环最终可找出x。在这过程中，定义一个变量t，令其在每次循环中都+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;

}

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;

}

4,.算法时间和空间复杂度：

算法时间复杂度为O（log n），此算法时间复杂度为while循环次数，因为每次查找范围减半，因此最坏情况下要执行（log n）次循环。、

空间复杂度为O（1），此算法使用辅助空间存储相应变量，与问题规模大小无关因此空间复杂度为O（1）

5.心得体会

对于除了做作业很少动手的我来说，这次结队做题让我认识了自己的不足，同时也体会到了有能够共同交流的伙伴的重要性