# include "iostream.h"
# include "stdlib.h"
void search(int *a,int j)
{
	int s,m,l,h;
	l=1;
	h=j;
	cout<<"輸入你要用二分查找的數；";
	cin>>s;
	do
	{
		m=(l+h)/2;
		if(s==a[m])
		{
			cout<<"the result's number is:"<<m<<endl;
			exit(0);
		}
			else if(s>a[m])
			    l=m+1;
		      else h=m-1;
	}while(l<=h);
	cout<<"There is no result you want."<<endl;
}
void exchange(int &a,int &b)
{
	int m;
	m=a;
	a=b;
	b=m;
}
int partition(int *a,int p,int r)
{
	int j;
	int x=a[r];
	int i=p-1;
	for(j=p;j<=r-1;j++)
	{
		if(a[j]<=x)
		{
	     i=i+1;
		 exchange(a[i],a[j]);
		}
	}
	exchange(a[i+1],a[r]);
	return i+1;
}
void quicksort(int *a,int p,int r)
{
	int q;
	if(p<r)
	{
		q=partition(a,p,r);
	    quicksort(a,p,q-1);
	    quicksort(a,q+1,r);
	}
}
void merge(int *a,int p,int q,int r)
{
	int k,i,j;
	int n1=q-p+1;
	int n2=r-q;
	int *L=new int[n1+2];
	int *R=new int[n2+2];
	for(i=1;i<=n1;i++)
		L[i]=a[p+i-1];
	for(j=1;j<=n2;j++)
		R[j]=a[q+j];
	L[n1+1]=6536;
	R[n2+1]=6536;
	i=j=1;
	for(k=p;k<=r;k++)
	{
		if(L[i]<R[j])
		{
			a[k]=L[i];
			i=i+1;
		}
		else {
			a[k]=R[j];
			j=j+1;
		}
	}
	delete L;
	delete R;
}
void mergesort(int *a,int p, int r)
{
	int q;
	if(p<r)
	{
		q=(p+r)/2;
		mergesort(a,p,q);
		mergesort(a,q+1,r);
		merge(a,p,q,r);
	}
}
void main()
{
	int i,j;
	cout<<"請輸入你要輸入數組的個數：";
	cin>>j;
	int *a=new int[j+1];
	a[0]=0;
	cout<<"請輸入你要排序的數組："<<endl;
	for(i=1;i<=j;i++)
		cin>>a[i];
	mergesort(a,1,j);
		for(i=1;i<j+1;i++)
		cout<<a[i]<<",";
		cout<<endl;
	search(a,j);
	delete a;
}