算法分析与设计实验报告

——二分搜索程序算法的实现

实验目的及要求

1.理解分治算法的概念和基本要素；
2.理解递归的概念；
3.掌握设计有效算法的分治策略；
4.通过二分搜索技术学习分治策略设计技巧；

实验环境

操作系统：Windows 10 操作系统
开发工具：Eclipse(4.15.0)
开发语言：Java

实验内容

1.使用二分搜索算法查找有序数列中的指定元素；
2.通过上机实验进行算法实现；
3.保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

算法描述及实验步骤

实验步骤：

1. 编写二分搜索算法；
2. 将输入的数组元素排序，转化成有序列；
3. 编写输入输出；
4. 测试结果。

调试过程及实验结果

问题1：编写递归方法时返回的边界错误，导致陷入死循环。如
return RecursionBinarySearch(arr,key,left,middle);//搜索左半区
return RecursionBinarySearch(arr,key,middle,right);//搜索右半区

正确修改：return RecursionBinarySearch(arr,key,left,middle-1);
return RecursionBinarySearch(arr,key,middle+1,right);

问题2：编写迭代方法时while()的条件写成while(left<right)遗漏等号，导致搜索值key=arr[arr.length]时，输出“未搜索到key”。
正确修改：while(left<=right)
输出结果为：

总结

元素存储在数组中，因此搜索输出的结果为有序数组元素的下标。
若有序列中存在重复元素，搜索结果输出第一个元素的下标。
对二分搜索算法的边界问题要考虑清楚， 循环体外的初始条件与循环体内的步骤一定要遵守一致的区间规则（左右开闭），否则会发生陷入死循环、无法找到搜索元素的错误。
二分搜索算法是将数列按有序化排列，查找过程中采用跳跃式方式查找，先以有序数列的中点位置为比较对象，如果查找的元素值小于中点元素（key<middle），则将待查序列缩小为左半区间，否则为右半区间，直到找到相同元素，或者查找范围为空。
二分搜索算法的优点是比较次数少，查找速度快，平均性能好；缺点是要求待查表为有序表，且插入删除困难。

源代码

import java.util.Scanner;
public class BinarySearch{	
	public static int RecursionBinarySearch(int[] arr , int key , int left , int right)
	{	//递归
		if((key<arr[left]||(key>arr[right])||(right>right)))
				return -1;
		int middle =(left &right) + ((left ^ right) >> 1); //防溢出(left &right) + ((left ^ right) >> 1);
		if(key<arr[middle])
		{
			return RecursionBinarySearch(arr,key,left,middle-1);//搜索左半区
		}
		else if(key>arr[middle]) 
		{
			return RecursionBinarySearch(arr,key,middle+1,right);//搜索右半区
		}
		else
		{
			return middle;
		}
	}
	
	public static int CommonBinarySearch(int[] arr,int key) 
	{	//迭代
		int left = 0;
		int right = arr.length-1;
		int middle = 0;
		if((key<arr[left])||(key>arr[right]))
			return -1;
		while(left<=right)  
			{
				middle =(left &right) + ((left ^ right) >> 1);
				if(key==arr[middle])
					return middle;
				else if(key<arr[middle])
					right = middle-1;//左半区搜索
				else if(key>arr[middle])
					left = middle+1;//右半区搜索
			}
		return -1;//未搜索到目标key返回-1
	}
	
	public static int[] Selectionsort(int[] arr) 
	{//选择排序
		for(int i=0;i<arr.length-1;i++)
		{
			int min = i;
			for(int j=i+1;j<arr.length;j++)
			{
				if(arr[j]<arr[min])
					min = j;
			}
			if(i!=min) 
			{
				int temp=arr[i];
				arr[i]=arr[min];
				arr[min]=temp;
			}
		}
		return arr;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("输入元素个数：");
		int n = sc.nextInt();
		int position;
		
		int[] arr = new int[n];//输入数组元素
		for(int i=0;i<n;i++)
		{
			System.out.print(i+"号元素为：");
			arr[i] = sc.nextInt();
		}
		
		Selectionsort(arr);//选择排序数组元素
		System.out.println("选择排序(升序)后有序列为：");
		for(int i=0;i<arr.length;i++)
		{
			System.out.print(arr[i]+" ");
		}
		System.out.println("");
		
		do {
			System.out.println("输入查找元素key：");
			int key =sc.nextInt();
			//递归搜索
			 position = RecursionBinarySearch(arr,key,0,arr.length-1);
			if(position==-1)
			{
				System.out.println("查找"+key+",有序列中不存在");
			}
			else
			{
				System.out.println("查找"+key+"（递归）\n"+"在有序列中的位置为："+position);
			}
			//迭代搜索
			  position = CommonBinarySearch(arr,key);
			if(position==-1)
			{
				System.out.println("查找"+key+",有序列中不存在");
			}
			else
			{
				System.out.println("查找"+key+"(迭代)\n"+"在有序列中的位置为："+position);
			}
			
		}while(true);
		
	}
	
	
}

算法分析与设计实验报告——二分搜索算法的实现

一、 实验目的

掌握分治法的基本思想，建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求

用c++语言实现二分搜索算法，分析时间复杂性。实现二分搜索的递归与非递归程序，并进行跟踪分析其执行过程，体会两者的执行效率。

三、 实验原理

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。

四、 实验过程(步骤)

见附件一
实验步骤、特点
重要源代码（流操作的部分要醒目的提示并注释）

五、 运行结果

见附件二

六、实验分析与讨论

编写程序时由于传参错误，导致结果不能输出，一直输出没有找到，然后更改了参数之后，程序输出就正确了。还有数组的大小计算不能用strlen函数，要用sizeof（a）/sizeof（a[0]）。
遇到的问题，及解决方案

七、实验特色与心得

这是我第一次实质上应用分治法编写程序。二分搜索算法能够实现O（logn）的时间复杂度，比一般的顺序搜索快了不少。这次实验也加深了我对分治法的理解。

附件一 实验过程(步骤)

二分搜索的递归程序：

#include <bits/stdc++.h>
using namespace std;
template<class Type>
int BinarySearch2(Type a[],const Type &x,int left,int right) //递归算法
{
    int middle=(left+right)/2;
    if(x==a[middle])//查找成功，返回下标
    {
        return middle;
    }
    if(left>=right)
    {
        return -1;
    }
    else if(x>a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x
    {
        return BinarySearch2(a,x,middle+1,right);
    }
    else if(x<a[middle])//如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x
    {
        return BinarySearch2(a,x,left,middle-1);
    }
    return -1;
}
int main()
{
    int x,len,b1,b2;
    int a[]= {1,2,3,4,5,6,7,8,9,10};//初始化a数组
    len=sizeof (a) / sizeof (a[0]);//计算a数组的长度
    cout<<"请输入您需要查找的数：";
    cin>>x;
    b2=BinarySearch2(a,x,0,len);
    if(b2==-1)
        cout<<"递归方法未找到"<<endl;
    else
        cout<<"递归方法："<<x<<" 的位置是第 "<<b2<<" 位"<<endl;
return 0;
}

二分搜索的非递归程序：

#include <bits/stdc++.h>
using namespace std;
template<class Type>
int BinarySearch1(Type a[],const Type &x,int n) //非递归算法
{
    int left = 0;
    int right = n-1;
    while(left <= right)
    {
        int middle = (left+right)/2;
        if(x == a[middle])//查找成功，返回下标
            return middle;
        if(x > a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x
            left = middle + 1;
        else//如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x
            right = middle - 1;
    }
    return -1;
}
int main()
{
    int x,len,b1,b2;
    int a[]= {1,2,3,4,5,6,7,8,9,10};//初始化a数组
    len=sizeof (a) / sizeof (a[0]);//计算a数组的长度
    cout<<"请输入您需要查找的数：";
    cin>>x;
    b1=BinarySearch1(a,x,len);
    if(b1==-1)
        cout<<"迭代方法未找到"<<endl;
    else
        cout<<"迭代方法："<<x<<" 的位置是第 "<<b1<<" 位"<<endl;
    return 0;
}

附件二 运行结果

a[]= {1,2,3,4,5,6,7,8,9,10};
二分搜索的递归程序运行结果：

a[]= {1,2,3,4,5,6,7,8,9,10};
二分搜索的非递归程序运行结果：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
//这个算法仅适用于有序序列
int a[1000];
int BinarySearch1(int a[], int left, int right, int x)
{
	int mid;
	mid = (left + right) / 2;
	if(left < right) {
		if (x == a[mid])
			return mid;
		else if (x < a[mid])
			return BinarySearch1(a, left, mid - 1, x);//递归调用前一半数组
		else
			return BinarySearch1(a, mid + 1, right, x);//。。。后一半。。。
	}
	return 0;
}
int BinarySearch2(int a[], int left, int right, int x)
{
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (x == a[mid])
			return mid;
		else if (x < a[mid])
			right = mid - 1;//递归调用前一半数组
		else
			left = mid + 1;//。。。后一半。。。
	}
	return 0;
}
int main()
{
	int x, n, flag = 0;
	cin >> x >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	flag = BinarySearch2(a, 1, n, x);
	if (flag)
		printf("%d", flag);
	else
		printf("no answer");
	return 0;
}

参考文章

https://blog.csdn.net/zsnowwolfy/article/details/81039836

https://blog.csdn.net/weixin_45929067/article/details/104781020