1_2_3.cpp

算法设计

/*题目：
设a[0:n-1]是已排好序的数组。请改写二分法搜索算法，
使得当搜索元素x不在数组中时，
返回小于x的最大元素位置i和大于x的最小元素的位置j。
当搜索元素在数组中时，i和j均相同，均在数组中的位置。
*/

/*题前分析：需要一个已排序的数组a[n]，
通过x与a[i]比较求i；有两种可能的结果。
为了方便起见，设这个数组为整型的！*/

#include<iostream>
using namespace std;
const int max=1000;//限定这个数组的长度，可以修改的
int a[max];
int inputA(int a[])//输入数组a的元素，并返还数组元素个数
{
	int n,i;
	try
	{
		while(n<0||n>max)
		{
			cout<<"请输入数组的长度n:";
			cin>>n;
		}
	}
	catch(int)
	{
		cout<<n<<"不是一个整型数据！\n";
	}//不知道为什么异常处理不起作用
	cout<<"请按增序或减序输入"<<n<<"个整数:\n";
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		if(i>=2)
		{
			if(!((a[i]<=a[i-1]&&a[i-1]<=a[i-2])||
				(a[i]>=a[i-1]&&a[i-1]>=a[i-2])))//判断序列是否为增序或减序
			{
				cout<<"输入错误！请重新输入：\n";//该判断只起一次作用
				for(i=0;i<n;i++)
					cin>>a[i];
			}
		}
	}
	return n;
}
int selectX(int x,int n)//折半查找的元素存在吗？存在则记录脚标
{
	int mid,low=0,high=n;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[0]<a[n-1])//递增排序
		{
			if(x<a[mid]) high=mid-1;
			else if(x>a[mid]) low=mid+1;
			else return mid+1;
		}
		if(a[0]>a[n-1])//递减排序
		{
			if(x<a[mid]) low=mid+1;
			else if(x>a[mid]) high=mid-1;
			else return mid+1;
		}	
	}
	return 0;
}
void insertX(int x,int n)
{
	int i,j;
	if(a[0]>a[1])//表示递减排序
	{
		if(x<a[n-1])
		{
			cout<<"比"<<x<<"大的最小元素的位置为："<<n<<endl;
			cout<<"没有比"<<x<<"小的元素！\n";
		}				
		if(x>a[0])
		{
			cout<<"比"<<x<<"小的最大元素的位置为："<<1<<endl;
			cout<<"没有比"<<x<<"大的元素！\n";
		}
		else
		{
			for(i=0;i<n;i++)
				if(x>a[i])//找到第一个比x小的a[i]
				{
					for(j=n;j>i;j--)
						a[j]=a[j-1];
					a[i]=x;
					break;
				}
		}
	}
	if(a[0]<a[1])//表示递增排序
	{
		if(x<a[0])
		{
			cout<<"比"<<x<<"大的最小元素的位置为："<<1<<endl;
			cout<<"没有比"<<x<<"小的元素！\n";
		}
		if(x>a[n-1])
		{
			cout<<"比"<<x<<"小的最大元素的位置为："<<n<<endl;
			cout<<"没有比"<<x<<"大的元素！\n";
		}
		else
		{
			for(i=0;i<n;i++)
				if(x<a[i])//找到第一个比x大的a[i]
				{
					for(j=n;j>i;j--)
						a[j]=a[j-1];
					a[i]=x;
					break;
				}
		}
	}
}
void main()
{
	int n,x;
	n=inputA(a);//完成数组a的数据输入，并返回数组元素个数
	cout<<"请输入你想要查询的元素x（x为整型）:";
	cin>>x;

	/*现在需要调用一个折半查找的函数，判断x是否在数组中。
	存在则返回脚标+1；如果所找元素不存在，则返回0。*/
	if(selectX(x,n)!=0)
	cout<<x<<"所在的位置是"<<selectX(x,n)<<endl;
	else
	{
	/*下面是对x元素在数组中不存在时的处理：
	将元素x按排序插入数组中，然后返回x的脚标+1*/
		if(n==0)
			cout<<"原数组中没有元素！\n";
		if(n==1)
		{
			if(x>a[0])
			{
				cout<<"比"<<x<<"小的最大元素的位置为："<<n<<endl;
				cout<<"没有比"<<x<<"大的元素！\n";
			}
			else
			{
				cout<<"比"<<x<<"大的最小元素的位置为："<<n<<endl;
				cout<<"没有比"<<x<<"小的元素！\n";
			}
		}
		else
		{
			insertX(x,n);
			if(a[0]>a[n])//递减排序
			{
				cout<<"比"<<x<<"小的最大元素的位置为"<<selectX(x,n)<<endl;
				cout<<"比"<<x<<"大的最小元素的位置为"<<selectX(x,n)-1<<endl;
			}
			if(a[0]<a[n])//递增排序
			{
				cout<<"比"<<x<<"小的最大元素的位置为"<<selectX(x,n)-1<<endl;
				cout<<"比"<<x<<"大的最小元素的位置为"<<selectX(x,n)<<endl;
			}
		}
	}
}