C ++程序使用二进制搜索方法查找给定数字的出现次数

Z时代
2024-01-10
分类：综合

这是一个使用Binary Search方法查找给定数字出现次数的C ++程序。

演算法

Begin

function Insert() to insert nodes into the tree:

Arguments:

root, d.

Body of the function:

Create node using data from argument list.

If tree is completely empty, then insert new node as root.

If d = tmp->data, increase the count of that particular node.

If d < tmp->data, move the tmp pointer to the left child.

If d > tmp->data, move the tmp pointer to the right child.

End

Begin

function SearchNode() to search item in the tree:

Arguments:

root, d.

Body of the function:

Run the for loop until temp points to a NULL pointer or data item is found.

If d < tmp->data, move the tmp pointer to the left child.

If d > tmp->data, move the tmp pointer to the right child.

If d = tmp->data, print the item found and it’s count and then return to main.

Else

Print data not found.

End

示例

#include<iostream>
using namespace std;
struct nod //declaration of node
{
   int data;
   int cnt;
   nod *l;
   nod *r;
};
nod* CreateNod(int d) //creation of new node
{
   nod *newnod = new nod;
   newnod->data = d;
   newnod->cnt = 1;
   newnod->l= NULL;
   newnod->r = NULL;
   return newnod;
}
nod* Insert(nod* root, int d) //perform insertion
{
   nod *tmp = CreateNod(d);
   nod *t = new nod;
   t = root;
   if(root == NULL)
      root = tmp;
   else {
      while(t != NULL) {
         if(t->data == d) {
            t->cnt++;
            break;
         } else if(t->data < d ) {
            if(t->r== NULL) {
               t->r= tmp;
               break;
            }
            t = t->r;
         } else if(t->data > d) {
            if(t->l== NULL) {
               t->l= tmp;
               break;
            }
            t = t->l;
         }
      }
   }
return root;
}
void SearchNode(nod *root, int d) //perform searching
{
   nod *tmp = new nod;
   tmp = root;
   while(tmp != NULL) {
      if(tmp->data == d) {
         cout<<"\nData item "<<d<<" is present "<<tmp->cnt<<" 次数。";
         return;
      } else if(tmp->data > d)
            tmp = tmp->l;
         else
            tmp = tmp->r;
   }
   cout<<"\n Data not found";
   return;
}
int main() {
   char c;
   int n, i, a[20] = {8,1,3,6,4,7,10,14,13,7,6,1,26,4,26,20,21,12,10,1}; //take the elements of the array
   nod *root = new nod;
   root = NULL;
   for(i = 0; i < 20; i++)
      root = Insert(root, a[i]);
      up:
      cout<<"\nEnter the Element to be searched: ";
      cin>>n;
      SearchNode(root, n);
      cout<<"\n\nWant to search more...enter choice(y/n)?";
      cin>>c;
      if(c == 'Y' || c == 'y')
         goto up;
      return 0;
}