#include <stdio.h>
#include <stdlib.h>

int *a;

int generateRandom(minRange,maxRange)
int minRange,maxRange;
{
/* returns integer in range minRange <= x <= maxRange*/
return minRange+abs(rand()) % (maxRange-minRange+1);
}

int intCompare(const void* xin, const void* yin)
{
int *x,*y;

x=(int*) xin;
y=(int*) yin;
return (*x) - (*y);
}

int intSearch(const void* keyIn, const void* arrayMemberIn)
{
int *key,*arrayMember;

key=(int*) keyIn;
arrayMember=(int*) arrayMemberIn;
return (*key) - (*arrayMember);
}

int intSearchLowEnd(const void* keyIn, const void* arrayMemberIn)
{
int *key,*arrayMember;

key=(int*) keyIn;
arrayMember=(int*) arrayMemberIn;
// Code here so that bsearch will find ptr to first array
// element that has the key.

}

int intSearchHighEnd(const void* keyIn, const void* arrayMemberIn)
{
int *key,*arrayMember;

key=(int*) keyIn;
arrayMember=(int*) arrayMemberIn;
// Code here so that bsearch will find ptr to last array
// element that has the key.

}

int mybsearch(int key,int *table,int n)
// Elementary binary search for an integer table with n keys
{
int low,high,mid;

low=0;
high=n-1;
while (1)
{
  mid=(low+high)/2;
  if (table[mid]==key)
    return mid;
  if (table[mid]<key)
    low=mid+1;
  else
    high=mid-1;
  if (low>high)
    return (-1);
}
}

int mybsearchlastsmaller(int key,int *table,int n)
// Finds the highest subscript for an array entry whose
// value is smaller than the supplied key
{
int low,high,mid;

low=0;
high=n-1;
while (1)
{
  mid=(low+high)/2;
// put code here
}
}

int mybsearchfirstlarger(int key,int *table,int n)
// Finds the lowest subscript for an array entry whose
// value is larger than the supplied key
{
int low,high,mid;

low=0;
high=n-1;
while (1)
{
  mid=(low+high)/2;
// put code here
}
}

main()
{
int i;
int *ptr,*lowPtr,*highPtr;
int sub,lowSub,highSub;
int sum;
int numslots,maxkey;

// Get table size and range of randomly generated keys
scanf("%d %d",&numslots,&maxkey);
a=(int*) malloc((numslots+2)*sizeof(int));
if (a==NULL)
  exit(0);
// initialize random number generator
srandom(1000);
a[0]=(-999);
for (i=1;i<numslots+1;i++)
  a[i]=generateRandom(0,maxkey);
a[numslots+1]=999999;
// UNIX quicksort call
qsort(&a[1],numslots,sizeof(int),intCompare);
if (numslots<21)
  for (i=0;i<numslots+2;i++)
    printf("%d %d\n",i,a[i]);
// Loop to check for any absent keys
for (i=0;i<=maxkey;i++)
{
  // Uses UNIX binary search routine for user-define key comparison
  ptr=(int*) bsearch(&i,&a[1],numslots,sizeof(int),intSearch);
  if (ptr==NULL)
    printf("%d not in table\n",i);
  else
    printf("%d occurs at subscript %d\n",i,ptr-a);
}
sum=0;
for (i=0;i<=maxkey;i++)
{
  lowPtr=(int*) bsearch(&i,&a[1],numslots,sizeof(int),intSearchLowEnd);
  if (lowPtr==NULL)
    printf("%d not in table\n",i);
  else
  {
    highPtr=(int*) bsearch(&i,&a[1],numslots,sizeof(int),intSearchHighEnd);
    if (highPtr==NULL)
      printf("FATAL:  intSearchHighEnd returned NULL\n");
    sum+=highPtr-lowPtr+1;
    printf("%d occurs %d times %d accumulated\n",i,highPtr-lowPtr+1,sum);
  }
}
printf("%d array elements classified\n",sum);
for (i=0;i<=maxkey;i++)
{
  sub=mybsearch(i,&a[1],numslots);
  if (sub==(-1))
    printf("%d not in table\n",i);
  else
    printf("%d occurs at subscript %d\n",i,sub+1);
}
sum=0;
for (i=0;i<=maxkey;i++)
{
  lowSub=mybsearchlastsmaller(i,&a[1],numslots)+2;
  highSub=mybsearchfirstlarger(i,&a[1],numslots);
//Next line is for debugging
//printf("key %d lowSub %d highSub %d\n",i,lowSub,highSub);
  sum+=highSub-lowSub+1;
  printf("%d occurs %d times %d accumulated\n",i,highSub-lowSub+1,sum);
}
printf("%d array elements classified\n",sum);
}