Posted on by Kalkicode
Code Array

# Count number of occurrences in a sorted array

Counting the number of occurrences of a specific element in a sorted array is a common problem in programming. Given a sorted array and a target element, the task is to determine how many times the target element appears in the array. This problem is essential for various applications, such as data analysis, statistics, and searching algorithms.

## Problem Statement

The problem can be stated as follows: Given a sorted array `arr` of size `n` and a target element `element`, count the number of occurrences of `element` in the array.

## Example

Consider the following sorted array `arr1` and target element `3`:

``````arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
element = 3``````

The element `3` appears 4 times in the array `arr1`, so the output should be: "Element 3 appears 4 times."

## Idea to Solve

Since the array is sorted, we can employ a binary search approach to efficiently find the target element's index. Once we find the index, we can traverse both sides of the index to count the occurrences.

## Pseudocode

``````function binary_search(arr, size, element):
i = 0
j = size - 1
while j >= i:
mid = (i + j) / 2
if arr[mid] > element:
j = mid - 1
else if arr[mid] < element:
i = mid + 1
else:
return mid
return -1

function count_occurrences(arr, size, element):
location = binary_search(arr, size, element)
if location >= 0:
counter = 1
temp = location + 1
while temp < size and arr[temp] == element:
counter++
temp++
temp = location - 1
while temp >= 0 and arr[temp] == element:
counter++
temp--
print("Element", element, "appears", counter, "times")
else:
print("Element", element, "does not exist")

// Example usage
arr = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
element = 3
count_occurrences(arr, size(arr), element)``````

## Algorithm Explanation

1. Perform a binary search to find the index of the target element in the array.
2. Once the index is found, initialize a counter to `1`.
3. Traverse to the right of the index and increment the counter for each occurrence of the target element.
4. Traverse to the left of the index and increment the counter for each occurrence of the target element.
5. Print the final count of occurrences.

## Code Solution

``````// C Program
// Count number of occurrences in a sorted array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Method which is finding given element index
int binary_search(int arr[], int size, int element)
{
//Defining variables are control execution process of function
int i = 0;
int j = (size - 1);
int mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
void count_occurrences(int arr[], int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
printf("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
printf(" Element %d are exists [%d] times\n", element, counter);
}
else
{
printf(" Element %d are not exists \n", element);
}
}
int main()
{
int arr1[] = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
count_occurrences(arr1, size, 3);
int arr2[] = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
count_occurrences(arr2, size, 8);
return 0;
}``````

#### Output

`````` Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````// Java Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public void count_occurrences(int[] arr, int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
System.out.print("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
System.out.print(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
System.out.print(" Element " + element + " are not exists \n");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = arr1.length;
obj.count_occurrences(arr1, size, 3);
int[] arr2 = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
}``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Count number of occurrences in a sorted array
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Method which is finding given element index
int binary_search(int arr[], int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
void count_occurrences(int arr[], int size, int element)
{
//Find the location of any given element
int location = this->binary_search(arr, size, element);
cout << "\n Array elements : ";
this->display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
cout << " Element " << element << " are exists [" << counter << "] times\n";
}
else
{
cout << " Element " << element << " are not exists \n";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.count_occurrences(arr1, size, 3);
int arr2[] = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
obj.count_occurrences(arr2, size, 8);
return 0;
}``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````//Include namespace system
using System;
// C# Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public void count_occurrences(int[] arr, int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
Console.Write("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
Console.Write(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
Console.Write(" Element " + element + " are not exists \n");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = arr1.Length;
obj.count_occurrences(arr1, size, 3);
int[] arr2 = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = arr2.Length;
obj.count_occurrences(arr2, size, 8);
}
}``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````<?php
// Php Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public	function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
//Method which is finding given element index
public	function binary_search( & \$arr, \$size, \$element)
{
//Defining variables are control execution process of function
\$i = 0;
\$j = (\$size - 1);
\$mid = 0;
//Search intermediate element
while (\$j > \$i)
{
//Get middle element
\$mid = intval((\$i + \$j) / 2);
if (\$arr[\$mid] > \$element)
{
//When middle element of index i and j are greater
\$j = \$mid - 1;
}
else if (\$arr[\$mid] < \$element)
{
//When middle element of index i and j are less
\$i = \$mid + 1;
}
else
{
return \$mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public	function count_occurrences( & \$arr, \$size, \$element)
{
//Find the location of any given element
\$location = \$this->binary_search(\$arr, \$size, \$element);
echo "\n Array elements : ";
\$this->display(\$arr, \$size);
if (\$location > 0)
{
\$counter = 0;
\$temp = \$location;
//Find next similar nodes
while (\$temp < \$size && \$arr[\$temp] == \$element)
{
\$counter++;
\$temp++;
}
\$temp = \$location - 1;
//Find previous similar nodes
while (\$temp >= 0 && \$arr[\$temp] == \$element)
{
\$counter++;
\$temp--;
}
echo " Element ". \$element ." are exists [". \$counter ."] times\n";
}
else
{
echo " Element ". \$element ." are not exists \n";
}
}
}

function main()
{
\$obj = new MyArray();
\$arr1 = array(-2, -1, 2, 3, 3, 3, 3, 5, 5);
//Get the size of array
\$size = count(\$arr1);
\$obj->count_occurrences(\$arr1, \$size, 3);
\$arr2 = array(6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20);
//Get the size of array
\$size = count(\$arr2);
\$obj->count_occurrences(\$arr2, \$size, 8);
}
main();``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````// Node Js Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Method which is finding given element index
binary_search(arr, size, element)
{
//Defining variables are control execution process of function
var i = 0;
var j = (size - 1);
var mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = parseInt((i + j) / 2);
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
count_occurrences(arr, size, element)
{
//Find the location of any given element
var location = this.binary_search(arr, size, element);
process.stdout.write("\n Array elements : ");
this.display(arr, size);
if (location > 0)
{
var counter = 0;
var temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
process.stdout.write(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
process.stdout.write(" Element " + element + " are not exists \n");
}
}
}

function main()
{
var obj = new MyArray();
var arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5];
//Get the size of array
var size = arr1.length;
obj.count_occurrences(arr1, size, 3);
var arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20];
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
main();``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````#  Python 3 Program
#  Count number of occurrences in a sorted array
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

# Method which is finding given element index
def binary_search(self, arr, size, element) :
# Defining variables are control execution process of function
i = 0
j = (size - 1)
mid = 0
# Search intermediate element
while (j > i) :
# Get middle element
mid = int((i + j) / 2)
if (arr[mid] > element) :
# When middle element of index i and j are greater
j = mid - 1

elif(arr[mid] < element) :
# When middle element of index i and j are less
i = mid + 1
else :
return mid

return -1

#  Find the occurrence of elements in given sorted array
def count_occurrences(self, arr, size, element) :
# Find the location of any given element
location = self.binary_search(arr, size, element)
print("\n Array elements : ", end = "")
self.display(arr, size)
if (location > 0) :
counter = 0
temp = location
# Find next similar nodes
while (temp < size and arr[temp] == element) :
counter += 1
temp += 1

temp = location - 1
# Find previous similar nodes
while (temp >= 0 and arr[temp] == element) :
counter += 1
temp -= 1

print(" Element ", element ," are exists [", counter ,"] times\n", end = "")
else :
print(" Element ", element ," are not exists \n", end = "")

def main() :
obj = MyArray()
arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
# Get the size of array
size = len(arr1)
obj.count_occurrences(arr1, size, 3)
arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20]
# Get the size of array
size = len(arr2)
obj.count_occurrences(arr2, size, 8)

if __name__ == "__main__": main()``````

#### Output

`````` Array elements :   -2  -1  2  3  3  3  3  5  5
Element  3  are exists [ 4 ] times

Array elements :   6  7  7  7  8  8  8  8  8  9  9  20
Element  8  are exists [ 5 ] times``````
``````#  Ruby Program
#  Count number of occurrences in a sorted array
class MyArray

# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
print("\n")
end
# Method which is finding given element index
def binary_search(arr, size, element)

# Defining variables are control execution process of function
i = 0
j = (size - 1)
mid = 0
# Search intermediate element
while (j > i)

# Get middle element
mid = (i + j) / 2
if (arr[mid] > element)

# When middle element of index i and j are greater
j = mid - 1
elsif(arr[mid] < element)

# When middle element of index i and j are less
i = mid + 1
else

return mid
end
end
return -1
end
#  Find the occurrence of elements in given sorted array
def count_occurrences(arr, size, element)

# Find the location of any given element
location = self.binary_search(arr, size, element)
print("\n Array elements : ")
self.display(arr, size)
if (location > 0)

counter = 0
temp = location
# Find next similar nodes
while (temp < size && arr[temp] == element)

counter += 1
temp += 1
end
temp = location - 1
# Find previous similar nodes
while (temp >= 0 && arr[temp] == element)

counter += 1
temp -= 1
end
# Display result
print(" Element ", element ," are exists [", counter ,"] times\n")
else

print(" Element ", element ," are not exists \n")
end
end
end
def main()

obj = MyArray.new()
arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
# Get the size of array
size = arr1.length
obj.count_occurrences(arr1, size, 3)
arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20]
# Get the size of array
size = arr2.length
obj.count_occurrences(arr2, size, 8)
end
main()``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
``````
``````// Scala Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Method which is finding given element index
def binary_search(arr: Array[Int], size: Int, element: Int): Int = {
//Defining variables are control execution process of function
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = ((i + j) / 2).toInt;
if (arr(mid) > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr(mid) < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
def count_occurrences(arr: Array[Int], size: Int, element: Int): Unit = {
//Find the location of any given element
var location: Int = binary_search(arr, size, element);
print("\n Array elements : ");
display(arr, size);
if (location > 0)
{
var counter: Int = 0;
var temp: Int = location;
//Find next similar nodes
while (temp < size && arr(temp) == element)
{
counter += 1;
temp += 1;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr(temp) == element)
{
counter += 1;
temp -= 1;
}
//Display result
print(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
print(" Element " + element + " are not exists \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr1: Array[Int] = Array(-2, -1, 2, 3, 3, 3, 3, 5, 5);
//Get the size of array
var size: Int = arr1.length;
obj.count_occurrences(arr1, size, 3);
var arr2: Array[Int] = Array(6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20);
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
}``````

#### Output

`````` Array elements :  -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times

Array elements :  6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times``````
``````// Swift Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Method which is finding given element index
func binary_search(_ arr: [Int], _ size: Int, _ element: Int) -> Int
{
//Defining variables are control execution process of function
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
func count_occurrences(_ arr: [Int], _ size: Int, _ element: Int)
{
//Find the location of any given element
let location: Int = self.binary_search(arr, size, element);
print("\n Array elements : ", terminator: "");
self.display(arr, size);
if (location > 0)
{
var counter: Int = 0;
var temp: Int = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter += 1;
temp += 1;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter += 1;
temp -= 1;
}
print(" Element ", element ," are exists [", counter ,"] times\n", terminator: "");
}
else
{
print(" Element ", element ," are not exists \n", terminator: "");
}
}
}
func main()
{
let obj: MyArray = MyArray();
let arr1: [Int] = [-2, -1, 2, 3, 3, 3, 3, 5, 5];
//Get the size of array
var size: Int = arr1.count;
obj.count_occurrences(arr1, size, 3);
let arr2: [Int] = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20];
//Get the size of array
size = arr2.count;
obj.count_occurrences(arr2, size, 8);
}
main();``````

#### Output

`````` Array elements :   -2  -1  2  3  3  3  3  5  5
Element  3  are exists [ 4 ] times

Array elements :   6  7  7  7  8  8  8  8  8  9  9  20
Element  8  are exists [ 5 ] times``````

## Time Complexity

• The binary search takes `O(log n)` time.
• Counting occurrences on both sides takes at most `O(n)` time in total.
• Overall, the time complexity of the algorithm is `O(log n + n)`, which simplifies to `O(n)`.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post