算法实验报告----1

一、? 实践题目

第一题：二分查找

二、? 问题描述

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

三、? 算法描述

1.关键部分算法描述：

?

int binary_search(vector<int>v,int key)

{

?? ???????int left=1,right=v.size()-1,mid;

?? ???????while(left<=right)

?? ??????{

????? ??????? mid=(left+right)/2;

????? ??????? if(v[mid]<key) left=mid+1;

????? ??????? else if(v[mid]>key) right=mid-1;

????? ??????? else if(v[mid]==key) return mid;

? ???? ??}

?? ??? ??return -1;

}

??????? ? 2.首先查找这个序列是有序的，从中间开始查找，如果小于或大于中间值，那么相应的最高和最低下标就要更改为中间值减一或加一。如此重复直到找到相应的值为止。

四、? 算法时间及空间复杂度分析（要有分析过程）

时间复杂度：O(h)=O(log2n)

?

???????????????? 设共有n个元素，

??????? 经过while（）的n值由n,n/2,n/4,…,n/2^k，由于n/2^k要取整，即令n/2^k = 1，可得k = log2n.

???????????????? 空间复杂度：0(n) = 1

???????

???????????????? 没有申请其他空间。

五、? 心得体会（对本次实践收获及疑惑进行总结）

1. 一个组进行编写代码，效率比自己一个编写的时候要高。因为不用再某个地方卡很久，会有组员相互解释。

?

? ? ? ? ?2.更深一步理解了二分法，我觉得二分法是比较容易理解也比较容易实现的算法，但是二分法的要求是顺序存储以及数据都按照一定的规律排好序的，要求比较多，我们在实际应用的时候要根据需求灵活使用。

?

? ? ? ? ?3．PTA上的错误有时候让人摸不着头脑，我们应该怎么提高答题的准确率呢？