0 votes
42 views
in Data Structure And Algorithm by (3.7k points)
Count number of occurrences (or frequency) in a sorted array in java.

int arr[] = {2,3,3,3,3};
int x = 3;

Output:- 4

1 Answer

0 votes
by (3.9k points)

I have given the following code to count the number of occurrences or frequency in sorted array. The Time Complexity of following code is O(logN).

package com.dev.search;

public class CountOccurenceOfElements {

public static void main(String[] args) {

int arr[] = {2,3,3,3,3};

int x = 3;

int count = getCountOccurence(arr, x);

System.out.println("Count of Occurence: " + count);

}

//Time Complexity O(logN) + O(logN) = O(logN)

private static int getCountOccurence(int[] arr, int x) {

//Time Complexity O(logN)

int lmostIndex = findLeftMostIndex(arr, x);

//Time Complexity O(logN)

int rmostIndex = findRightMostIndex(arr, x);

return rmostIndex-lmostIndex+1;

}

private static int findLeftMostIndex(int[] arr, int x) {

return findLeftMostIndex(arr, 0, arr.length-1, x);

}

private static int findRightMostIndex(int[] arr, int x) {

return findRightMostIndex(arr, 0, arr.length-1, x);

}

//Time Complexity O(logN)

private static int findLeftMostIndex(int[] arr, int l, int h, int x) {

if(l>h) {

return -1;

}

int mid = l+(h-l)/2;

if(arr[mid]==x) {

if(mid == 0 || arr[mid-1] != x) {//mid =0 means search data placed into 0 index

return mid;

}else {

return findLeftMostIndex(arr, l, mid-1, x);

}

}else if(x > arr[mid]) {

return findLeftMostIndex(arr, mid+1, h, x);

}else if(x < arr[mid]) {

return findLeftMostIndex(arr, l, mid-1, x);

}

return -1;

}

//Time Complexity O(logN)

private static int findRightMostIndex(int[] arr, int l, int h, int x) {

if(l>h) {

return -1;

}

int mid = l+(h-l)/2;

if(arr[mid]==x) {

if(mid == h || arr[mid+1] != x) {//mid =0 means search data placed into 0 index

return mid;

}else {

return findRightMostIndex(arr, mid+1, h, x);

}

}else if(x > arr[mid]) {

return findRightMostIndex(arr, mid+1, h, x);

}else if(x < arr[mid]) {

return findRightMostIndex(arr, l, mid-1, x);

}

return -1;

}

}

Output:- 
Count of Occurence: 4

Share:- Whatsapp Facebook Facebook


Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

...