#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
const n=100;
int s[n];
void seqsrch(int n, const int s[], int x, int &loc, int &co1);
void binsrch(int n, const int s[], int x, int &loc, int &co2);
void merge(int low , int mid , int high);
void mergesort(int low , int high);
void main()
{
	clrscr;
	randomize();
	int i,x,loc,co1=0,co2=0;
	int low=0,high=n-1;
	for(i=0;i<n;i++)
		s[i]=random(100);
	cout<<"This Number Added Randomize And Sorted By MergeSort...";
	mergesort(low,high);
	for(i=0;i<n;i++)
	{
		if (co1%10==0)
			cout<<"\n\n";
		cout<<s[i]<<setw(4);
		co1++;
	}
	cout<<"\n\nEnter A Number For Search:";
	cin>>x;
	co1=0;
	seqsrch(n,s,x,loc,co1);
	if (loc!=-1)
		cout<<"\n\nNumber Of Comparison Of Sequental Search = "<<co1;
	else
	{
		cout<<"\n\nNumber Not Exist In List...";
		getch();
		return;
	}
	co2=0;
	binsrch(n,s,x,loc,co2);
	if (loc!=-1)
		cout<<"\n\nNumber Of Comparison Of Binery Search = "<<co2;
	getch();
}
//****************************************************
void seqsrch(int n, const int s[], int x, int &loc, int &co1)
{
	int i;
   loc=-1;
	for(i=0;i<n;i++)
	{
		co1++;
		if (s[i]==x)
		{
			loc=i;
			return;
		}
	}
}
//****************************************************
void binsrch(int n, const int s[], int x, int &loc, int &co2)
{
	int low=0,mid,high=n-1;
	loc=-1;
	while(low<=high)
	{
      co2++;
		mid=(low+high)/2;
		if (x==s[mid])
		{
			loc=mid;
			return;
		}
		else if(x<s[mid])
			high=mid-1;
		else
			low=mid+1;
	}
}

//****************************************************
void mergesort(int low , int high)
{
   int mid;
   if (low<high)
   {
      mid=(low+high)/2;
      mergesort(low,mid);
      mergesort(mid+1,high);
      merge(low,mid,high);
   }
}
//****************************************************
void merge(int low , int mid , int high)
{
   int i=low,j=mid+1,k=low,a;
   int u[n];
   while(i<=mid && j<=high)
   {
      if(s[i]<s[j])
      {
	 u[k]=s[i];
	 i++;
      }
      else
      {
	 u[k]=s[j];
	 j++;
      }
      k++;
   }
   if(i>mid)
      for(a=j;a<=high;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   else
      for(a=i;a<=mid;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   for(a=low;a<=high;a++)
      s[a]=u[a];
}