#include <fstream>
#include <iostream>
#include <string>
#include <locale>
#include "math.h"
#include <stdlib.h>
#include <time.h>
using namespace std;
int Left(int i);
int Right(int i);
void swap(int *a,int *b);
void Max_Heapify(int *A,int i,int n);
void Build_Max_Heap(int *A,int n);
void Heapsort(int *A,int n);
int find(int *A,int *B,int n);//find the median element

  
main()
{
  int A[6]={61,17,30,50,83,39};
  int B[6]={2,27,198,25,4,18};
  int n=6;
  int i;
  Heapsort(A,n);
  Heapsort(B,n);
  cout<<"A= ";
  for(i=0;i<n;i++)
    cout<<A[i]<<" ";
  cout<<endl<<"B= ";
  for(i=0;i<n;i++)
    {
     cout<<B[i]<<" ";
    }
  cout<<endl;
  find(A,B, n);    
  return 0;
}


int Left(int i)
{
  return 2*i;
}
int Right(int i)
{
  return 2*i+1;
}

void swap(int *a,int *b)
{
  
    {
     int c=*a;
     *a=*b;
     *b=c;
    }
}
void Max_Heapify(int *A,int i,int n)
{
  int l=Left(i),r=Right(i);
  int largest;
  if(l<n&&A[l]>A[i])
    largest=l;
  else
    largest=i;
  if(r<n&&A[r]>A[largest])
    largest=r;
  if(largest!=i)
    {
     swap(A[i],A[largest]);
     Max_Heapify(A,largest,n);
    }
}
void Build_Max_Heap(int *A,int n)
{
  for(int i=n/2;i>=0;i--)
    Max_Heapify(A,i,n);
}
void Heapsort(int *A,int n)
{
  Build_Max_Heap(A,n);
  for(int i=n-1;i>0;i--)
    {
      swap(A[0],A[i]);
      n--;
      Max_Heapify(A,0,n);
    }
}
int find(int *A,int *B,int n)//find the median element
{
  int start=1,end=n,value,a,b;
  while(1)
    {
      b=(start+end)/2;  //get position
      cout<<"Alice sends Bob position: "<<b<<endl;
      value=B[b-1];    //get value
      cout<<"Bob sends Alice value B["<<b<<"]: "<<value<<endl;
      a=n-b;
      if(value>A[a-1])   
	{
          if(a<n&&value<A[a]||a==n)
	    {
	     cout<<"The median element is B["<<b<<"]="<<value<<endl;
             return 1;    //get the result,return
	    }
          else
	    end=b-1;      //look for in barkward    
             
	}
      else if(value<A[a-1])
	   {
             if(b<n&&B[b]>A[a-1]||b==n)
	       {
                cout<<"The median element is A["<<a<<"]="<<A[a-1]<<endl;
                return 1;

	       }
             else
               {
		 start=b+1; //look for in forward
	       }
	   }
         else
           {
             cout<<"Error!"<<endl;
	   }
     }
             
}