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.

New Comment