// Demonstration of special binary searches for tables with duplicates. // No input. Output is how many times each number in // -1 .. 20 appears in a table. #include int a[20]={0,1,1,1,2,4,4,6,6,6, 10,12,12,12,12,15,15,17,17,18}; 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. { int low,high,mid; low=0; high=n-1; // Subscripts between low and high are in search range. // Size of range halves in each iteration. // When low>high, low==high+1 and a[high]=key. while (low<=high) { mid=(low+high)/2; if (a[mid]high, low==high+1 and a[high]<=key and a[low]>key. while (low<=high) { mid=(low+high)/2; if (a[mid]<=key) low=mid+1; else high=mid-1; } return high; } int 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); } }