二分搜索算法实验报告

实验一 二分搜索算法实验报告

一． 实验目的

1、 理解分治算法的概念和基本要素； 2、 理解递归的概念；

3、 掌握设计有效算法的分治策略；

4、 通过二分搜索技术学习分治策略设计技巧；

二．实验内容及要求

1． 使用二分搜索算法查找任意N个有序数列中的指定元素。 2． 通过上机实验进行算法实现。

3． 保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 4. 至少使用两种方法进行编程。

三．实验原理

二分搜索算法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

【基本思想】将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二

分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

? 方法一：直接查找

穷举法遍历 ? 方法二：递归查找

#include #define MAX 30

int BinarySearch(int a[],int &x,int left,int right) {

if(left>right){ return -1; } else{

left=(left+right)/2; if(x==a[left]) return left; else {

if(x>a[left])

BinarySearch(a,x,left+1,right); else

BinarySearch(a,x,left*2-right,left+1); } } }

main() {

int a[MAX];

int found,x,n,i,j,p; printf(\输的个数\\n\ scanf(\

printf(\数组数据\\n\ for(i=0;i

scanf(\ }

for (i=0;i

p=i;

for (j=i+1;ja[j]) p=j; if (p!=j) {

x=a[p]; a[p]=a[i]; a[i]=x; } }

for(i=0;i

printf(\ \ }

printf(\输入要查找的数\\n\ scanf(\

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

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

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

? 方法三：迭代查找

#include #define MAX 30

int BinarySearch(int a[],int &x,int n) {

int left =0; int right=n-1; int middle;

while(left<=right){

middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1;

else right=middle-1; }

return-1; }

main() {

int a[MAX];

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

printf(\数组数据\\n\ for(i=0;i

scanf(\ }

for (i=0;i

p=i;

for (j=i+1;ja[j]) p=j; if (p!=j) {

x=a[p]; a[p]=a[i]; a[i]=x; } }

for(i=0;i

printf(\ \ }

printf(\输入要查找的数\\n\ scanf(\

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

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

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

}

四．程序代码

变量定义说明：

BinarySearch()算法： a->数组

key->要查找的元素 left->左标志 right->右标志 （n->数据个数）

Main()主函数： ound->是否找到标志，-1表示未找到，找到其值为下标

x->要查找的元素 n->元素个数

i，j，p->循环控制变量

（1）、递归查找

#include #define MAX 30

int BinarySearch(int a[],int key,int left,int right) {

int mid=(right-right)/2+left; if(a[mid]==key) { return mid; }

if(left>=right) { return -1;

}else if(key>a[mid]) {

return BinarySearch(a,key,mid+1,right); } else if(key

return BinarySearch(a,key,left,mid- 1); }

return -1; }

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

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

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