C ++程序使用二进制搜索方法查找数组的最小元素

这是一个使用线性搜索方法查找数组的最小元素的C ++程序。该程序的时间复杂度为O(log(n))。

算法

Begin

   Construct binary search tree for the given unsorted data array.

   To find out the minimum element move the pointer to the leftmost child node.

   Print this value as minimum value among the given data.

End

范例程式码

#include<iostream>

using namespace std;

struct node {

   int d;

   node *left;

   node *right;

};

node* CreateNode(int d) {

   node *newnode = new node;

   newnode->d = d;

   newnode->left = NULL;

   newnode->right = NULL;

   return newnode;

}

node* InsertIntoTree(node* root, int d) {

   node *temp = CreateNode(d);

   node *t = new node;

   t = root;

   if(root == NULL)

      root = temp;

   else{

      while(t != NULL) {

         if(t->d < d) {

            if(t->right == NULL) {

               //如果当前节点为NULL,则插入该节点。

               t->right = temp;

               break;

            }

            //将指针向左移动。

            t = t->right;

         }

         else if(t->d > d) {

            if(t->left == NULL) {

               t->left = temp;

               break;

            }

            t = t->left;

         }

      }

   }

   return root;

}

int main() {

   int n, i, a[10]={86, 63, 95, 6, 7, 67, 52, 26, 45, 98};

   node *root = new node;

   root = NULL;

   cout<<"\nData set:\n";

   for(i = 0; i < 10; i++) {

      cout<<a[i]<<" ";

      root = InsertIntoTree(root, a[i]);

   }

   cout<<"\n\nThe minimum element of the given data set is ";

   i = 0;

   while(root->left != NULL) {

      i++;

      root = root->left;

   }

   cout<<root->d<<" which found at "<<i<<" 从根开始的深度。";

   return 0;

}

输出结果

Data set:

86 63 95 6 7 67 52 26 45 98

The minimum element of the given data set is 6 which found at 2 从根开始的深度。

以上是 C ++程序使用二进制搜索方法查找数组的最小元素 的全部内容, 来源链接: utcz.com/z/331267.html

回到顶部