4
\$\begingroup\$

Input: Array of sorted integers and an element to check the frequency for

Output: Frequency of the element

public class FrequencyElement {
public static void main(String args[]){
    //System.out.println("Enter Input string");

    int input_array []= {2,3,4,25,99,99,19000};
    int element = 99;

    System.out.println(checkFreq(input_array,element));
}
static int checkFreq(int a[],int n){
    //returns the frequency of n in a

    int indexOfElement=elementExists(a,n);

    if(indexOfElement!=-1){
        int count =0;
        while(a[indexOfElement]==n){
            count++;
            indexOfElement++;
        }
        return count;
    }
    else
        return 0;

}
static int elementExists(int input[], int element){
    int lo=0;
    int high = input.length-1;

    while(lo<high){
        int mid = (lo + high )/2;
        if(element >input[mid] ){
            lo = mid+1;
        }
        else if(element < input[mid]){
            high= mid-1;
        }
        else if (lo !=mid)
            high = mid;
        else {
            System.out.println("Mid is: " + mid);
            return mid;
        }
    }
    return -1;
}
}
\$\endgroup\$

3 Answers 3

6
\$\begingroup\$

Reinventing the wheel

There is already a binary search available in JDK.

Bug

On the array {2,3,4,25,99,99,99,99,19000} your implementation returns 0. Removing the lines

else if (lo !=mid)
    high = mid;

from elementExists seems to fix the issue.

Printing from an algorithm

System.out.println("Mid is: " + mid);

It is not a good idea to print to stdout from an algorithm; at least not in the production code. Think about what happens if your friend uses your code: he gets overwhelmed with all the output + I/O is usually computationally expensive.

Summa summarum

All in all, I had this in mind:

import java.util.Arrays;

public class FrequencyElement {

    public static void main(String args[]) {
        int input_array[] = {2, 3, 4, 25, 99, 99, 19000};
        int element = 99;
        System.out.println(getElementFrequency(input_array, element));
    }

    static int getElementFrequency(final int array[], final int queryElement) {
        final int index = getElementIndex(array, queryElement);

        // If there is more than one query elements. Arrays.binarySearch does 
        // not guarantee that the index returned will point to the left most
        // occurrence.
        if (index < 0) {
            return 0;
        }

        int count = 1; // Count array[index].
        int offset = 1;

        while (index - offset >= 0 && queryElement == array[index - offset]) {
            ++offset;
            ++count;
        }

        offset = 1;

        while (index + offset < array.length 
                && queryElement == array[index + offset]) {
            ++offset;
            ++count;
        }

        return count;
    }

    private static int getElementIndex(final int[] array, 
                                       final int queryElement) {
        return Arrays.binarySearch(array, queryElement);
    }
}

Hope that helps.

\$\endgroup\$
3
\$\begingroup\$
int indexOfElement=elementExists(a,n);

Semantic type cast error - elementExists sounds like something that will either give you "true", because the element exists, or "false", because the element does not exist. Instead, it returns integer. You should rename the method to "findIndexOf"

    else if (lo !=mid)
        high = mid;
    else {

ALWAYS add braces. This sort of thing looks confusing.

if(indexOfElement!=-1){
    int count =0;
    while(a[indexOfElement]==n){
        count++;
        indexOfElement++;
    }
    return count;
}
else
    return 0;

You'd be better off first explicitly handling the case where the element was not found, as it reduces indentation required.

if (indexOfElement == -1) {
   return 0;
}

int count = 0;
while (a[indexOfElement] == n) {
    count++;
    indexOfElement++;
}
return count;

Lastly, you should consider the case where the entire array is a single value.

You will get ArrayIndexOutOfBoundsException. You must check if the array is within length. Two solutions for this: either check for this in the while (while (a.length > indexOfElement && a[indexOfElement] == n)) or, check beforehand if the last element in the array is not n and use this to guarantee you won't run off the edge.

\$\endgroup\$
1
\$\begingroup\$

I can remember, that one of my professors told us about a complete binary search algorithm (in the formal way), which guarantees to find the least index of an element. You can find the description here on page 35 (binary search).

Note that this algorithm has fewer comparisons and array access but sligthly more iterations. Here is the special binary search:

private static int leastIndexOf(int[] arr, int e) {
  int left = 0, right = arr.length;
  while (left != right) {
    int mid = left + right >>> 1;
    if (arr[mid] < e) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  if (left != arr.length && arr[left] == e) {
    return left;
  } else {
    return -1;
  }
}

There are already clean implementations of counting but just for completness:

public static int frequency(int[] arr, int e) {
  Objects.requireNonNull(arr);
  int index = leastIndexOf(arr, e);
  if (index < 0) {
    return 0;
  } else {
    int count = 0;
    for (int i = index; i < arr.length && arr[i] == e; i++) {
      count++;
    }
    return count;
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.