Algotree > Algorithms > Binary Search > Finding count of duplicate numbers in a sorted array using binary search

Finding count of duplicate numbers in a sorted array using binary search

Finding the count of duplicate numbers in a sorted array using binary search

Binary Search looks for a value in a sorted array. It compares the middle element of the array with the searched value. If the middle element equals the searched value, the position of the middle element is returned. If the middle element is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched using binary search.

Algorithm for finding duplicates makes use of binary search to find the first occurrence and the last occurrence of the element to be searched.

Finding the first occurrence
If the searched element located at index mid and its previous element (i.e at index mid-1) match, binary search continues in the sorted space to the left side of index mid i.e from index beg till index mid-1. This way the search continues until the previous element is the same as the element to be searched. When the search terminates we get the index of the first occurrence.
Finding the last occurrence
If the searched element located at index mid and its next element (i.e at index mid+1) matches the searched value, the search continues in the sorted space to the right side of mid i.e from index mid+1 till index end. When the search terminates we get the index of the last occurrence.

Thus, count of duplicate elements = Index of the last occurrence - Index of the first occurrence + 1

Example of finding the count of duplicate numbers using binary search Binary_Search_Duplicates

Time complexity of finding count of duplicate numbers using binary search in a sorted array : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?

Java

Java : Binary Search implementation to find the count of duplicate numbers within a sorted array in Java 8

public class FindDuplicates {

    int FirstOccurrence (int[] array, int n) {

        int beg = 0;
        int end = array.length - 1;

        while (beg <= end) {

            int mid = beg + (end-beg)/2;

            if (array[mid] == n) {
                if (mid-1 >= 0 && array[mid-1] == n) {
                   end = mid-1;
                   continue;
                }
                return mid;
            }

            else if (array[mid] < n)
                beg = mid + 1;
            else
                end = mid - 1;
        }
        return -1;
    }

    int LastOccurrence (int[] array, int n) {

        int beg = 0;
        int end = array.length - 1;

        while (beg <= end) {

            int mid = beg + (end-beg)/2;

            if (array[mid] == n) {
                if (mid+1 <= array.length && array[mid+1] == n) {
                   beg = mid + 1;
                   continue;
                }
                return mid;
            }

            else if (array[mid] < n)
                beg = mid + 1;
            else
                end = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {

        int[] array = { 1, 2, 3, 9, 9, 9, 9, 10, 10, 12, 13 };
        int first_index, last_index, n;
        n = 9;

        FindDuplicates fd = new FindDuplicates();

        first_index = fd.FirstOccurrence(array, n);
        last_index =  fd.LastOccurrence(array, n);

        if (first_index == -1 || last_index == - 1) {
            System.out.println("Element does not exist");
        } else {
            System.out.println("First Occurrence of " + n + " is at index : " + first_index);
            System.out.println("Last Occurrence of " + n + " is at index : " + last_index);
            System.out.println("Total Count : "+ (last_index - first_index + 1));
        }

        fd = null;
    }
}

Output of Binary Search implementation to find the count of duplicate elements in an array

First Occurrence of 9 is at index : 3
Last Occurrence of 9 is at index : 6
Total Count : 4

Python

Python : Binary Search implementation to find the count of duplicate numbers within a sorted array in Python 3

#!/usr/bin/python3

def FirstOccurrence ( array, n) :
    
    beg = 0;
    end = len(array) - 1;

    while (beg <= end) :

        mid = int (beg + (end-beg)/2)

        if (array[mid] == n) :
            if (mid-1 >= 0 and array[mid-1] == n) :
               end = mid-1
               continue

            return mid 

        elif (array[mid] < n) :
            beg = mid + 1 
        else :
            end = mid - 1 

    return -1  

def LastOccurrence (array, n) :
    
    beg = 0;
    end = len(array)-1

    while (beg <= end) :

        mid = int(beg + (end-beg)/2)

        if (array[mid] == n) :
            if (mid+1 <= len(array) and array[mid+1] == n) :
               beg = mid + 1 
               continue
            return mid 

        elif (array[mid] < n) :
            beg = mid + 1 
        else :
            end = mid - 1;

    return -1; 

array = [ 1, 2, 3, 9, 9, 9, 9, 10, 10, 12, 13 ]
n = int (input("Enter the number : "))

first_index = FirstOccurrence (array, n)
last_index  = LastOccurrence (array, n); 

if (first_index == -1 or last_index == - 1) :
    print("Element does not exist")
else :
    print("First Occourance of " + str(n) + " is at index : " + str(first_index))
    print("Last Occourance of " + str(n) + " is at index : " + str(last_index))
    print("Total Count : "+ str(last_index - first_index + 1))

Output of Binary Search implementation to find the count of duplicate elements in an array

Enter the number : 9
First Occourance of 9 is at index : 3
Last Occourance of 9 is at index : 6
Total Count : 4

Enter the number : 10
First Occourance of 10 is at index : 7
Last Occourance of 10 is at index : 8
Total Count : 2

Enter the number : 5
Element does not exist

Enter the number : 12
First Occourance of 12 is at index : 9
Last Occourance of 12 is at index : 9
Total Count : 1

C++ : Binary Search implementation to find the count of duplicate numbers within a sorted array in C++11

#include<iostream>
#include<vector>

using namespace std;

int FirstOccurrence (vector<int> &, int);
int LastOccurrence (vector<int> &, int);

int FirstOccurrence (vector<int> &vec, int n) { 
    
    int beg = 0;
    int end = vec.size() - 1;

    while (beg <= end) {

        int mid = beg + (end-beg)/2;

        if (vec[mid] == n) {
            if (mid-1 >= 0 and vec[mid-1] == n) { 
               end = mid-1;
               continue;
            }
            return mid;
        }
    
        else if (vec[mid] < n)
            beg = mid + 1;
        else
            end = mid - 1;
    }   
    return -1; 
}

int LastOccurrence (vector<int> &vec, int n) { 
    
    int beg = 0;
    int end = vec.size()-1;

    while (beg <= end) {

        int mid = beg + (end-beg)/2;

        if (vec[mid] == n) {
            if (mid+1 <= vec.size() and  vec[mid+1] == n) { 
               beg = mid + 1;
               continue;
            }
            return mid;
        }

        else if (vec[mid] < n)
            beg = mid + 1;  
        else
            end = mid - 1;
    }   
    return -1; 
}

int main()
{
   vector<int> vec = { 1, 2, 3, 9, 9, 9, 9, 10, 10, 12, 13 };

   int first_index, last_index, n;
   n = 9;

   first_index = FirstOccurrence (vec, n); 
   last_index =  LastOccurrence (vec, n); 

   if (first_index == -1 or last_index == - 1) { 
       cout << "Element does not exist" << endl;
   } else {
       cout << "First Occourance of " << n << " is at index : " << first_index << endl;
       cout << "Last Occourance of " << n << " is at index : " << last_index << endl;
       cout << "Total Count : " << last_index - first_index + 1;
   }   
   return 0;
}

Output of Binary Search implementation to find the count of duplicate elements in an array

First Occourance of 9 is at index : 3
Last Occourance of 9 is at index : 6
Total Count : 4