// Demonstration of special binary searches for tables with duplicates,
// but using bsearch().
// No input.  Output is how many times each number in
// -1 .. 20 appears in a table.
#include <stdio.h>
#include <stdlib.h>

int a[20]={0,1,1,1,2,4,4,6,6,6,
           10,12,12,12,12,15,15,17,17,18};

int intCompareFirst(const void* xin, const void* yin)
// Used in calls to bsearch()
{
if (*((int*) xin) <= *((int*) yin))
  if (*((int*) xin) <= *(((int*) yin)-1))
    return -1;
  else
    return 0;
else
  return +1;
}

int binSearchFirst(int *a,int n,int key)
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the first a element >= key.
//         Returns n if key>a[n-1].
// Processing: Binary search using bsearch().
{
  if (key>a[n-1])
    return n;
  if (a[0]>=key)
    return 0;
  return (int*) bsearch(&key,&a[1],n-1,sizeof(int),intCompareFirst)
                - a; // ptr arithmetic
}

int intCompareLast(const void* xin, const void* yin)
// Used in calls to bsearch()
{
if (*((int*) xin) >= *((int*) yin))
  if (*((int*) xin) >= *(((int*) yin)+1))
    return +1;
  else
    return 0;
else
  return -1;
}

int binSearchLast(int *a,int n,int key)
{
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search using bsearch().
  if (key<a[0])
    return -1;
  if (a[n-1]<=key)
    return n-1;
  return (int*) bsearch(&key,a,n-1,sizeof(int),intCompareLast)
                - a; // ptr arithmetic
}

main()
{
int i,first,last,key;

printf("-- table --\n");
for (i=0;i<20;i++)
  printf("%3d %3d\n",i,a[i]);
printf("key  first  last  count\n");
for (i=(-1);i<21;i++)
{
  first=binSearchFirst(a,20,i);
  last=binSearchLast(a,20,i);
  printf("%3d   %3d   %3d   %3d\n",i,first,last,last-first+1);
}
}