Ronzii's Blog

Just your average geek's blog

Count the number of occurrences in a sorted array

Algorithm
  1. Use Binary search to get index of the first occurrence of x in arr[] (i)
  2. Use Binary search to get index of the last occurrence of x in arr[] (j)
  3. Return (j – i + 1)
#include <iostream>
using namespace std;
int lower_bound(int a[],int low,int high, int x)
{
    if(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==x && (a[mid-1]<x || mid==0)) return mid;
        if(x<a[mid])
            return lower_bound(a,low,mid-1,x);
        else
            return lower_bound(a,mid+1,high,x);
    }
    return -1;
}
int upper_bound(int a[],int low,int high, int x, int n)
{
    if(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==x && (a[mid+1]>x || mid==n-1)) return mid;
        if(x<a[mid])
            return upper_bound(a,low,mid-1,x,n);
        else
            return upper_bound(a,mid+1,high,x,n);
    }
    return -1;
}
int count(int a[],int n,int x)
{
    int i = lower_bound(a,0,n-1,x);
    if(i==-1) return 0;
    int j = upper_bound(a,0,n-1,x,n-1);
    return j-i+1;
}
int main()
{
    int a[] = {1,1,1,40,40,40,110};
    int n = sizeof(a)/sizeof(a[0]);
    cout<<count(a,n,40)<<endl;
    return 0;
}
Advertisements

March 26, 2012 Posted by | C++ | , , , , | Leave a comment