Number of occurrences of element

Given a sorted array and a key, find number of occurrences of key in that array. For example, in below array, number of occurrences of 3 is 3.

number of occurrences of element

Brute force method will be to scan through array, find first instance of element and then find last instance, then do the math. Complexity of that method is O(N). Can we do better than that?

Did you get some hint when brute force method was described? Yes,we have already cracked the problem to find first occurrence and last occurrence in O(log n) complexity earlier. We will be using those two methods, all we need to do know is math.

occurrences = lastInstance - firstInstance + 1

Number of occurrences of element : Implementation.

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean isGreaterThanEqualTo(int[] a, int index, int key){
        if(a[index] >= key) return true;

        return false;
    }

    public static int findFirstInstance(int[] a, int start, int end, int key){

        while(start < end){
            int mid = start + (end - start) / 2;

            if(isGreaterThanEqualTo(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }

        return (a[start] == key) ? start : -1;
    }

    private static boolean isLessThanEqualTo(int[] a, int index, int key){
        if(a[index] <= key) return true;

        return false;
    }

    public static int findLastInstance(int[] a, int start, int end, int key){

        while(start < end){
            int mid = start +( (end - start) + 1) / 2;

            if(isLessThanEqualTo(a, mid, key)){
                start = mid;
            }
            else{
                end = mid - 1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

    public  static  int numberOfOccurrences(int[] a, int key){
        int firstInstance = findFirstInstance(a, 0, a.length-1, key);
        int lastInstance = findLastInstance(a, 0, a.length-1, key);

        return (firstInstance != -1) ? lastInstance-firstInstance + 1 : 0;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,17,17,20};

        int index = numberOfOccurrences(input,3);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Worst case time complexity of algorithm to find number of occurrences of element in sorted array is O(log n). We are using iterative method to find first and last instances, therefore, there is no hidden space complexity of algorithm.

Please share if there is something wrong or missing. Also if you want to contribute to algorithms and me, please drop an email at communications@algorithmsandme.com