Write a program to perform a binary search on an unsorted list of n integers?

Answer 1

#include<iostream>

#include<iomanip>

#include<vector>

#include<random>

// The node class is used to store a value from the

// unsorted list, along with its index in the list.

// The left node points to a tree of nodes where

// all values are less than this node's value. The

// right node points to a tree of nodes where all

// values are greater than (or equal to) this node.

struct node

{

unsigned value;

unsigned index;

node* left;

node* right;

node (unsigned val, unsigned idx)

: value (val), index (idx),

left(NULL), right (NULL) {}

~node ()

{

delete left;

delete right;

}

void insert (node& n)

{

if (n.value<value)

{

if (left)

left->insert (n);

else

left = &n;

}

else

{

if (right)

right->insert (n);

else

right = &n;

}

}

node* find (unsigned val)

{

if (val == value)

return this;

else if (val < value)

return left ? left->find (val) : NULL;

else

return right ? right->find (val) : NULL;

}

};

// The tree class maintains the root node of a binary

// search tree (BST). The default constructor builds

// a BST from a vector of values. All other methods

// delegate to the root node.

struct tree

{

node* root;

tree (const std::vector<unsigned>& v)

: root (NULL)

{

for (unsigned i=0; i<v.size(); ++i)

{

node* n = new node(v[i], i);

if (!root)

root = n;

else

root->insert (*n);

}

}

~tree ()

{

delete root;

}

node* find (unsigned value)

{

return root ? root->find (value) : NULL;

}

};

// A helper function to determine if a value exists

// in a vector or not.

bool exists(std::vector<unsigned> vect, unsigned num)

{

for (unsigned i=0; i<vect.size(); ++i)

if (vect[i] == num )

return true;

return false;

}

int main()

{

// random number generator (range: 1 to 15)

std::default_random_engine generator;

std::uniform_int_distribution<unsigned> distribution (1, 15);

// create an unsorted list with 10 random numbers and print them

// in the order they are generated

std::vector<unsigned> vect;

std::cout << "Unsorted list: ";

unsigned nums = 10;

while (nums--)

{

do

{

unsigned num = distribution (generator);

// ensure num is unique!

if (!exists (vect, num))

{

vect.push_back (num);

std::cout << std::setw(3) << vect.back();

break;

}

} while (true);

}

std::cout <<std::endl;

// create a binary search tree from the vector

tree bst (vect);

// now go find all the numbers in the tree and show where they

// reside in the list (include all the missing numbers)

for (unsigned num=1; num<=15; ++num)

{

if( node* n = bst.find (num))

{

std::cout << num << " was found in the tree";

std::cout << " and is at index " << n->index;

std::cout << " in the list" << std::endl;

}

else

std::cout << num << " could not be found in the tree" << std::endl;

}

}