Skip to main content

Count number of occurrences in a sorted array

Here given code implementation process.

// 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




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