二分搜索算法实验报告

{ printf(\请输入第%d个数据:\ scanf(\ }

for (i=0;ia[j]) p=j; if (p!=j) { x=a[p]; a[p]=a[i]; a[i]=x; } }

printf(\排序后的数据如下：\ for(i=0;i

printf(\ }

printf(\

printf(\输入要查找的数:\ scanf(\ int left=0,right=n;

found=BinarySearch(a,x,left,right); if(found==-1) {

printf(\未找到\\n\ } else {

printf(\要查找的数在第%d个\\n\ } }

（2）、非递归查找

#include #define MAX 30

int BinarySearch(int a[], int key,int len){ int mid=len/2; if (key==a[mid]) { return mid;

}

int left=0;

int right=len-1;

while(left<=right){ //迭代查找 mid=(right+left)/2; if(keya[mid]) { left=mid+1; }else{

return mid; } }

return -1; }

int main(void) { int a[MAX];

int found,x,n,i,j,p; printf(\数据个数:\ scanf(\

printf(\输入数据:\\n\ for(i=0;i

for (i=0;ia[j]) p=j; if (p!=j) { x=a[p]; a[p]=a[i]; a[i]=x; } }

printf(\排序后的数据如下：\ for(i=0;i

printf(\

}

printf(\

printf(\输入要查找的数:\ scanf(\ int left=0,right=n;

found=BinarySearch(a,x,n); if(found==-1) {

printf(\未找到\\n\ } else {

printf(\要查找的数在第%d个\\n\ } }

五．结果运行与分析

找到要查找的数据：

未找到要查找的数据：

六．心得与体会

通过这次实验，巩固了自己对二分搜索算法的理解，它是分治法的一个特殊例子，由此也对分治法有了更深一层次的认识。分而治之，化复杂为简单，不只是在算法中，在日常生活中也是极其重要的。正如Bentley在他的著作《Writing Correct Programs》中所说，能够完整的写出二分搜索算法是很难的，准确来说，在固定的时间内很大一部分人是不能完成这个任务的，因为其中的边界判定问题需要引起很大的注意，一不留神就容易犯错，导致结果的错误，而这种边界问题有很难找到，只有通过一步一步的演算才能完全正确的推导出来。这告诫我们，熟能生巧，只有在生活中多练习，当真正需要的时候，才能够信手拈来。