Monday, November 30, 2015

Count the number of occurrence of an element in an array using Binary Search


    public int FindNumberOfOccurancesInArray(int element, int[] input)    {
        int first=BinarySearchFindIndex(element, input, true);
        if(first==-1)//Doesn't have the element
            return 0;
        else    {
            int second=BinarySearchFindIndex(element, input, false);
            System.out.println(first+" "+second);
            return second-first+1;
        }
    }


This is a module to perform Binary Search
if firstElement = true -> Binary Search returns first occurrence of an element
if firstElement = false -> Binary Search returns last occurrence of an element

    public int BinarySearchFindIndex(int element, int[] input, boolean firstElement)    {
         int high = input.length;
        int low = 0;
        int result =-1;
        while(low<=high)    {
            int mid = low + ((high-low)/2);
            if(element==input[mid])    {
                result = mid;
                if(firstElement)
                    high=mid-1;
                else
                    low=mid+1;
            }    else if(element<input[mid])    {
                high=mid-1;
            }    else if(element>input[mid])    {
                low=mid+1;
            }
        }
        return result;
    }
UA-39217154-2