Question

Suppose I have a list of 128 unsorted numbers. If I use the binary search to search it, how many comparisons will I have to do in the worst case, assuming I use a quadratic algorithm to sort the list first.

Answer 1

Hi,

Sorting is the process of ordering the elements in an array. There are different types of sorting techniques.

For 128 unsorted numbers of a list the comparisons in worst case will be: 9

Binary Search algorithm:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<process.h>
struct tree
{  
int data;
struct tree *left;
struct tree *right;
};
struct tree *create();
void preorder(struct tree *);
void inorder(struct tree *);
void postorder(struct tree *);
struct tree *create()
{
struct tree *p,*root;
int m,x;
char s;
root=(struct tree *)malloc(sizeof(struct tree));
printf("\nenter the value of the main root");scanf("%d",&m);
root->data=m;
root->left=NULL;
root->right=NULL;
printf("\nEnter (y/n) to creation of the binary search tree :");
fflush(stdin);
scanf("%c",&s);
while(s!='n')
{
p=root;
printf("\nenter the value of the newnode");
fflush(stdin);
scanf("%d",&x);
while(1)
{
if(x<p->data)
{
if(p->left==NULL)
{
p->left=(struct tree *)malloc(sizeof(struct tree));
p=p->left;
p->data=x;
p->right=NULL;
p->left=NULL;
break;
}
else
p=p->left;
}
else
{
if(p->right==NULL)
{
p->right=(struct tree *)malloc(sizeof(struct tree));
p=p->right;
p->data=x;
p->right=NULL;
p->left=NULL;
break;
}
else
p=p->right;
}
}
printf("\nwant to continue-- press (y/n)");
fflush(stdin);
scanf("%c",&s);
}
return(root);
}
void preorder(struct tree *p)
{
if(p!=NULL)
{
printf("%d ",p->data);
preorder(p->left);
preorder(p->right);
}
}
void inorder(struct tree *p)
{
if(p!=NULL)
{
inorder(p->left);
printf("\t%d",p->data);
inorder(p->right);
}
}
void postorder(struct tree *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf("\t%d",p->data);
}
}
void main()
{
int h;
struct tree *root;
clrscr();
while(1)
{
printf("\n1. for creation of the binary search tree");
printf("\n2. for preorder traversal");
printf("\n3. for inorder traversal");
printf("\n4. for postorder traversal");
printf("\n5. for exit");
printf("\nEnter your choice: ");
scanf("%d",&h);
switch(h)
{
case 1:
root=create();
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
case 5:
exit(0);
default:
printf("\nEntered a wrong choice.");
}
}
}