Count the number of occurrences of a element in a sorted array

The following solutions describe how to count the number of occurrences of a particular element in a sorted array in which the elements are repeated.

1. Using Linear Search algorithm
2. Using Binary Search algorithm to find the element and count its occurrences
3. Using Binary Search algorithm to find the first occurrence and last occurrence of the element and count the total number of occurrences

Using Linear Search algorithm

Do a linear search over the array and increment count as and when you find the element  ‘K’ in the array

Time Complexity – O(n)

Dry run for the following example:

Input: a[8] = {1,2,3,4,4,4,4,5} and K = 4

count = 0;

i=0: a[0] = 1 <> 4. So count = 0

i=1: a[1] = 2 <> 4. So count = 0

i=2: a[2] = 3 <> 4. So count = 0

i=3: a[3] = 4 = 4. So count = 1

i=4: a[4] = 4 = 4. So count = 2

i=5: a[5] = 4 = 4. So count = 3

i=6: a[6] = 4 = 4. So count = 4

i=7: a[7] = 5 <> 4. So count = 4

Total number of occurrences for element 4 is count = 4

Code for the above problem is as follows:

public class LinearSearchCount
{
    public LinearSearchCount()
    {
    }

    public static int countNumberOfOccurances(int[] a, int n, int k)
    {
        int resultSearchValue = linearSearchCount(a, n, k);

        if (resultSearchValue == -1)
        {
            return 0;
        }
        else
        {
            return resultSearchValue;
        }
    }

    public static int linearSearchCount(int[] a, int n, int k)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
        {
            if (a[i] == k)
            {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args)
    {
        //  Input Array
        int[] a = { 1, 2, 3, 4, 4, 4, 4, 5 };

        //  k - Element to be found
        int k = 4;

        //  n - Size of the array
        int n = 8;
        System.out.println(countNumberOfOccurances(a, n , k));
    }
}

Using Binary Search algorithm to find the element and count its occurrences

Do a binary search for the element ‘K’ in the array. Let its position be i.

Now traverse towards left and count the number of occurrences of K. Let this count be leftCount.

Similarly, traverse towards right and count the number of occurrences of K. Let this count be rightCount.

Total number of occurrences – leftCount + 1 + rightCount

Time Complexity – O(logn + S) where S is the number of occurrences

Dry run for the following example:

Input: a[8] = {1,2,3,4,4,4,4,5} and K = 4

Binary search to find i:

Iteration 1: low = 0; high = 7; mid = 3

a[3] = 4 = 4. Return mid as 3;

Therefore i =3.

Traverse towards left:

a[i-1] = a[2] = 3 <> 4. leftCount = 0 and stop traversing left

Therefore leftCount =0.

Traverse towards right:

a[i+1] = a[4] = 4 == 4. rightCount = 1

a[i+1] = a[5] = 4 == 4. rightCount = 2

a[i+1] = a[6] = 4 == 4. rightCount = 3

a[i+1] = a[7] = 5 <> 4. rightCount = 3 and stop traversing right

Therefore rightCount = 3.

Total number of occurrences = leftCount + 1 + rightCount = 0 + 1 + 3 = 4

Code for the above problem is as follows:

public class BinaryLinearSearch
{
    public BinaryLinearSearch()
    {
    }

    public static int countNumberOfOccurances(int[] a, int n, int k)
    {
        int i = binarySearch(a, 0, n - 1, k);

        if (i == -1)
        {
            return 0;
        }
        else
        {
            int leftCount = 0;

            if ((i - 1) > 0)
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    if (a[j] == k)
                    {
                        leftCount++;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            int rightCount = 0;

            if ((i + 1) < n)
            {
                for (int j = i + 1; j <= n; j++)
                {
                    if (a[j] == k)
                    {
                        rightCount++;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            return leftCount + 1 + rightCount;
        }
    }

    public static int binarySearch(int[] a, int low, int high, int k)
    {
        if (high >= low)
        {
            int mid = (low + high) / 2;

            if (a[mid] == k)
            {
                return mid;
            }
            else if (a[mid] < k)
            {
                return binarySearch(a, mid + 1, high, k);
            }
            else
            {
                return binarySearch(a, low, mid - 1, k);
            }
        }

        return -1;
    }

    public static void main(String[] args)
    {
        //  Input Array
        int[] a = { 1, 2, 3, 4, 5, 5, 5, 6 };

        //  k - Element to be found
        int k = 5;

        //  n - Size of the array
        int n = 8;
        System.out.println(countNumberOfOccurances(a, n, k));
    }
}

Using Binary Search algorithm to find the first occurrence and last occurrence of the element and count the total number of occurrences

To find first Occurrence:

Condition for binary search to find first occurrence is as follows:

Return the position if any one of the following is true:

mid == 0 and a[mid] == K
a[mid] == K and a[mid-1] < K

To find last Occurrence:

Condition for binary search to find last occurrence is as follows:

Return the position if any one of the following is true:

mid == n and a[mid] == K where n is lenght of the array – 1
a[mid] == K and a[mid+1] > K

Total number of occurrences =  lastOccurrence – firstOccurrence + 1

Time Complexity – O(log n)

Code for the above problem is as follows:

public class BinarySearchCount
{
    public BinarySearchCount()
    {
    }

    public static int countNumberOfOccurances(int[] a, int n, int k)
    {
        int firstOccurrence = binarySearchfirstOccurrence(a, n, 0, n, k);
        int lastOccurrence = binarySearchlastOccurrence(a, n, 0, n, k);

        if ((firstOccurrence == -1) && (lastOccurrence == -1))
        {
            return 0;
        }
        else if (firstOccurrence == lastOccurrence)
        {
            return 1;
        }
        else
        {
            return (lastOccurrence - firstOccurrence + 1);
        }
    }

    public static int binarySearchfirstOccurrence(int[] a, int n, int low,
        int high, int k)
    {
        if (high >= low)
        {
            int mid = (low + high) / 2;

            if (((mid == 0) && (a[mid] == k)) ||
                    ((a[mid] == k) && (a[mid - 1] < k)))
            {
                return mid;
            }
            // Favor left half of the array
            else if (a[mid] >= k)
            {
                return binarySearchfirstOccurrence(a, n, low, mid - 1, k);
            }
            else
            {
                return binarySearchfirstOccurrence(a, n, mid + 1, high, k);
            }
        }

        return -1;
    }

    public static int binarySearchlastOccurrence(int[] a, int n, int low,
        int high, int k)
    {
        if (high >= low)
        {
            int mid = (low + high) / 2;

            if (((mid == n) && (a[mid] == k)) ||
                    ((a[mid] == k) && (a[mid + 1] > k)))
            {
                return mid;
            }
            // Favor right half of the array
            else if (a[mid] <= k)
            {
                return binarySearchlastOccurrence(a, n, mid + 1, high, k);
            }
            else
            {
                return binarySearchlastOccurrence(a, n, low, mid - 1, k);
            }
        }

        return -1;
    }

    public static void main(String[] args)
    {
        //  Input Array
        int[] a = { 1, 2, 3, 4, 5, 5, 5, 6 };

        //  k - Element to be found
        int k = 5;

        //  n - Size of the array
        int n = 8;
        System.out.println(countNumberOfOccurances(a, n - 1, k));
    }
}

Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.

Advertisements