Solution: Count Element Occurrence
Here is a detailed analysis of the different ways to count the frequency of a number in a sorted array of integers.
Solution #1: Brute force with linear search
Press + to interact
class Count {public static int calcFreq(int arr[], int key) {int count = 0;//traversing the arrayfor (int i = 0; i < arr.length; i++) {//checking if current index value matches keyif (arr[i] == key)//incrementing count if it doescount++;}return count;}public static void main(String args[]) {int arr[] = {-5,-3,0,1,3,3,3,3,4,5};int key = 3;System.out.println("The key \"" + key + "\" occurs " + calcFreq(arr, key) + " times in the Array.");}}
This is an extremely simple way to solve this problem. We simply initialize a variable, count
, to keep count and set it to 0 (line 3). We then iterate over the array (line 5), increasing count
by one every time the key
(value to search) is encountered (lines 7-9).
Time complexity
The time complexity of this algorithm is in since the array is iterated over once.
Solution #2: Using binary search
Press + to interact
main.java
Helper.java
class Count{public static int calcFreq(int[]arr, int key){int arrSize = arr.length;Helper obj = new Helper();int index = obj.binarySearch(key, arr, arrSize);if (index == -1) // If element is not presentreturn 0;int count = 1; // Initialzing a countint start = index - 1; // Counting the ones present on the leftwhile (start >= 0 && arr[start] == key) {count++;start--; // Decrement the start index if found}int end = index + 1; // Counting the ones present on the rightwhile (end < arrSize && arr[end] == key) {count++;end++; // Increment the end index if found}return count;}public static void main(String args[]){int arr[] = {-5,-3,0,1,3,3,3,3,4,5};int key = 3;System.out.println("The key \""+ key + "\" occurs " + calcFreq(arr, key) + " times in the Array.");}}
This is also a very simple solution. It draws upon the fact that if an element exists in a sorted array, all of its ...