C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Find the Number of occurrences of a given Number using Binary Search approach



Find the Number of occurrences of a given Number using Binary Search approach

- Implement binary search tree to find the number of occurrences of a given number.
- The worst case time complexity of Binary search is O(n) but for the average case, it is O(log(n)).

- Construct binary search tree for the given unsorted data array and maintain an additional count variable.
- If any element is repeated then increase the count of that node.
- Proceed with the search by comparing an element to the data of the node and print the count of that particular data element.
- Exit.

#include<iostream>
 
using namespace std;
 
// A structure representing a node of a tree.
struct node
{
	int data;
	int count;
	node *left;
	node *right;
};
 
// A function creating a new node of the tree and assigning the data.
node* CreateNode(int data)
{
	node *newnode = new node;
	newnode->data = data;
	newnode->count = 1;
	newnode->left = NULL;
	newnode->right = NULL;
 
	return newnode;
}
 
// A function creating binary search tree.
node* InsertIntoTree(node* root, int data)
{
	// Create node using data from argument list.
	node *temp = CreateNode(data);
	node *t = new node;
	t = root;
 
	// If root is null, assign it to the node created.
	if(root == NULL)
		root = temp;
	else	
	{
		// Find the position for the new node to be inserted.
		while(t != NULL)
		{
			// If the new data is already there then just increase the counter.
			if(t->data == data)
			{
				t->count++;
				break;
			}
			else if(t->data < data )
			{
				if(t->right == NULL)
				{
					// If current node is NULL then insert the node.
					t->right = temp;
					break;
				}
				// Shift pointer to the left.
				t = t->right;
			}
			else if(t->data > data)
			{
				if(t->left == NULL)
				{
					// If current node is NULL then insert the node.
					t->left = temp;
					break;
				}
				// Shift pointer to the left.	
				t = t->left;
			}
		}
	}
	return root;
}
 
// A function to search item in a BST.
void Search(node *root, int data)
{
	node *temp = new node;
	temp = root;
	// Run the loop until temp points to a NULL pointer or data element is found.
	while(temp != NULL)
	{
		if(temp->data == data)
		{
			cout<<"\nData item "<<data<<" is present "<<temp->count<<" number of times.";
			return;
		}
		// Shift pointer to left child.
		else if(temp->data > data)
			temp = temp->left;
		// Shift pointer to right child.
		else
			temp = temp->right;
	}
 
	cout<<"\n Data not found";
	return;
}
 
int main()
{
	char ch;
	int n, i, a[25] = {24, 17, 83, 8, 46, 37, 26, 92, 47, 43, 32, 26, 28, 17, 73, 28, 43, 22, 88, 43, 93, 81, 77, 23, 97};
	node *root = new node;
	root = NULL;
 
	// Construct the BST.
	for(i = 0; i < 25; i++)
		root = InsertIntoTree(root, a[i]);
 
	up:
	cout<<"\nEnter the Element to be searched: ";
	cin>>n;
 
	Search(root, n);
 
	// Ask user to enter choice for further searching.
	cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
	cin>>ch;
	if(ch == 'y' || ch == 'Y')
	goto up;
 
	return 0;
}