数据结构与算法之四 搜索算法

目标

在本章中，你将学习： 使用线性搜索技术搜索数据和二叉搜索技术搜索数据 

/*从8个数中查找数字*/
using System;

class Ban
{
	public static void Main(string[]args)
	{
		//int []arr={8001,8002,8003,8004,8007,8010,8005,8009}; //定义有8个整数的数组		
		Console.WriteLine("请输入您的工号个数:");
		int n; //n为数组的上界
		n=Convert.ToInt32(Console.ReadLine());	//n就是数组的长度（个数)
		
		int []arr=new int[n];		//定义有10个数字的数组
		for(int j=0;j<n;j++)
		{
			Console.Write("请输入第"+(j+1).ToString()+"个数:");
			arr[j]=Convert.ToInt32(Console.ReadLine());
		}		
		
		//3.重复步骤 4 直到 i > n 或 arr[i] = id 才退出.
	 char ch='y'; //定义我们不断查找的条件，如果为y|Y,则一直查找；n|N：则退出查找.
	 
	 while((ch=='y')||(ch=='Y'))
	 {
	 	Console.WriteLine("请输入您要查找的数字:");
	 	int id=Convert.ToInt32(Console.ReadLine());	//定义要查找的数据元素	
		
		int lowerbound=0;
		int upperbound=n-1;
		int mid=(lowerbound+upperbound)/2;	//中间值下标
		
		//13	 
		while(lowerbound<=upperbound)	//实现找合适的中间值索引
		{
			if(id<arr[mid])
				upperbound=mid-1;
			else
				lowerbound=mid+1;
				
			mid=(lowerbound+upperbound)/2;	
			Console.WriteLine("low:"+lowerbound+"mid:"+mid+"upper:"+	upperbound);	
		}
		//针对找到数据元素，代码
				Console.WriteLine(arr[mid]);
		if(id==arr[mid])
				Console.WriteLine("ok");
		else		
			Console.WriteLine("没有找到....");
			
		Console.WriteLine("您是否继续查找，是(y|Y),否(n|N):");
	  ch=Convert.ToChar(Console.ReadLine());	
	}//不断查找结束		
	}
}

/*使用二叉搜索在含有最多20个元素的数组中搜索一个数，假设数组是以升序输入的。如果数组中有多个要搜索的数，则发现一个匹配后搜索就停止了。
程序还应该显示所作的比较总数。
*/
using System;

class BinarySearch
{
	static void Main(string[]args)
	{
		int[]arr=new int[20];	//要搜索的数组
		int n;	//数组中的元素数
		int i;	//获取在数组中存储的元素数
		
		while(true)
		{
			Console.Write("请输入数组的元素个数:");
			string s=Console.ReadLine();
			n=Int32.Parse(s);
			if((n>0)&&(n<=20))
				break;
			else
				Console.WriteLine("\n数组最少1个元素，最多20个元素.\n");	
		}
		//接受数组元素
		Console.WriteLine("------------------------------------------");
		Console.WriteLine("---------------输入数组元素---------------");
		Console.WriteLine("------------------------------------------");
		
		for(i=0;i<n;i++)
		{
				Console.Write("<"+(i+1)+">");
				string s1=Console.ReadLine();
				arr[i]=Int32.Parse(s1);
		}
		char ch='y';
		do
		{
			//要搜索的数
			Console.Write("请键入您要查找的数");			
			int item=Convert.ToInt32(Console.ReadLine());
			//应用二叉搜索
			int lowerbound=0;
			int upperbound=n-1;
			
			//获取中间元素的索引
			int mid=(lowerbound+upperbound)/2;
			int ctr=1;
			
			while((item!=arr[mid])&&(lowerbound<=upperbound))	//在数组中搜索元素的循环
			{
				if(item>arr[mid])
					lowerbound=mid+1;
				else
					upperbound=mid-1;
				mid=(lowerbound+upperbound)/2;
				//ctr++;
			}
	
			if(item==arr[mid])
				Console.Write("\n"+item.ToString()+"发现了位置:"+(mid+1).ToString());
			else
				Console.Write("\n"+item.ToString()+"在数组中没有发现");
				Console.Write("\n比较次数:"+ctr);
				Console.Write("\n继续搜索(y/n)");
				ch=char.Parse(Console.ReadLine());
		}while((ch=='y')||(ch=='Y'));
}	
}

/*
编写一个在含有20个数的数中使用线性搜索算法一个给定数的程序，如果要搜索的元素在列表中出现多次，则该程序应该显示第一次出现的位置，还应该显示所作
的比较总数。
*/
using System;

class SequentialSearch
{
	static void Main(string[]args)
	{
		int[]arr=new int[20];	//要搜索的数组
		int n;								//数组中的元素
		int i;	//获取在数组中存储的元素
		
		while(true)
		{
			Console.Write("请输入数组的元素个数:");
			string s=Console.ReadLine();
			n=Int32.Parse(s);
			if((n>0)&&(n<=20))
				break;
			else
				Console.WriteLine("\n数组最少1个元素，最多20个元素.\n");	
		}
		//接受数组元素
		Console.WriteLine("------------------------------------------");
		Console.WriteLine("---------------输入数组元素---------------");
		Console.WriteLine("------------------------------------------");
		
		for(i=0;i<n;i++)
		{
				Console.Write("<"+(i+1)+">");
				string s1=Console.ReadLine();
				arr[i]=Int32.Parse(s1);
		}
		char ch='y';
		int  ctr;
		
		do
		{
			//接受要搜索的数
			Console.Write("\n请输入您要搜索的数:");
			int item=Convert.ToInt32(Console.ReadLine());
			//应用线性搜索
			ctr=0;
			for(i=0;i<n;i++)
			{
				ctr++;
				if(arr[i]==item)
				{
					Console.WriteLine("\n"+item.ToString()+"发现在位置"+(i+1).ToString());
					break;	
				}	
			}
			if(i==n)
			{
				Console.WriteLine("\n"+item.ToString()+"在数组中没有发现元素");
				Console.WriteLine("\n比较的次数为："+ctr);
				Console.Write("\n继续搜索(y/n):");
				ch=Char.Parse(Console.ReadLine());	
			}
		}while((ch=='Y')||(ch=='y'));
	}	
}

数据结构与算法之四 搜索算法

原文：http://blog.csdn.net/zhangchen124/article/details/51628351