Skip to content

Instantly share code, notes, and snippets.

@anil477
Created June 20, 2017 16:21
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anil477/d6111ac91f035d6f1bf300c7ee2d75ae to your computer and use it in GitHub Desktop.
Count number of occurrences (or frequency) in a sorted array
// http://www.geeksforgeeks.org/count-number-of-occurrences-or-frequency-in-a-sorted-array/
// the method returns first and last occurence of any given item.
// frequency = last - first + 1
class Frequency {
public static void main(String[] args) {
int[] arr={1, 1, 2, 2, 2, 2, 3};
//int[] arr={1, 1, 1, 1, 1, 1, 1};
//int[] arr = {1, 1, 1, 0, 0, 0, 0};
int x = 1;
first(arr, x);
last(arr, x);
}
public static void last(int[] a, int x)
{
int l = 0;
int h = a.length-1;
int mid = -1;
int n = a.length -1;
while(l<=h)
{
mid = (l+h)/2;
if( (mid == n || a[mid+1] > x) && a[mid] == x)
{
System.out.println("Last Occurence " + (mid));
return;
}
if(x < a[mid] )
{
h = mid - 1;
} else {
l = mid + 1;
}
}
System.out.println(" Not found ");
}
public static void first(int[] a, int x)
{
int l = 0;
int h = a.length-1;
int mid = -1;
while(l<=h)
{
mid = (l+h)/2;
if( (mid == 0 || a[mid-1] < x) && a[mid] == x)
{
System.out.println("First Occurence " + (mid));
return;
}
if( a[mid] < x)
{
l = mid + 1;
} else {
h = mid - 1;
}
}
System.out.println(" Not found ");
return;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment