Iterative Binary Search

When a list is ordered, there is a much better searching strategy Let us take for the example of card picking game I pick a number between 1 and 100, and you try to guess what it is. Each time you guess, I will tell you if your guess is correct, too high, or too low. What is your strategy?

If you play this game with a very young child, they might well adopt a strategy of simply guessing numbers at random. An older child might employ a systematic approach corresponding to linear search, guessing 1; 2; 3; 4; : : : until the mystery value is found.

Of course, virtually any adult will guess 50. If told that the number is higher, then the range of possible values is 50.100. The next logical guess is 75. Each time we guess the middle of the remaining numbers to try to narrow down the possible range. This strategy is called a binary search. Binary means two, and at each step, we are dividing the remaining numbers into two parts.

We can employ a binary search strategy to look through a sorted list. The basic idea is that we use two variables to keep track of the endpoints of the range in the list where the item could be. Initially, the target could be anywhere in the list, so we start with variables low and high set to and last positions of the list, respectively.

The heart of the algorithm is a loop that looks at the item in the middle of the remaining range to compare it to x. If x is smaller than the middle item, then we move top, so that the search is narrowed to the lower half. If x is larger, then we move low, and the search is narrowed to the upper half. The loop terminates when x is found or there are no longer any more places to look (i.e., low > high). Here is the code:

def search(x, nums)
low = 0
high = len(nums) - 1
while low <= high: # There is still a range to search
mid = (low + high) / 2 # position of middle item
item = nums[mid]
if x == item : # Found it! Return the index
13.1. Searching 429
return mid
elif x < item: # x is in lower half of range
high = mid - 1 # move top marker down
else: # x is in upper half
low = mid + 1 # move bottom marker up
return -1 # no range left to search,
# x is not there

This algorithm is quite a bit more sophisticated than the simple linear search.

Prims Algorithm

Prim's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. Prim's algorithm is an example of a greedy algorithm. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim-Jarník algorithm.



The algorithm works by starting from a randomnode and checks the minimum cost for all links for it, then goes to thesecond node and then checks again for the least cost for the two nodes,considering not to visit any visited node.

Program in C++


#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
#include”process.h”
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999
class point
{
public:
int pre,dist,status;
};
class arc
{
public:
int u,v;
};
int adj[MAX][MAX];
int n;
class graph
{
public:
void creategraph();
void display();
int allperm(class point state[MAX]);
int maketree(class arc tree[MAX],int *weight);
};
void graph::creategraph()
{
int i=0,max_arc,origin,destin,wt;
cout<<"\n Enter the number of vertices:";
cin>>n;
max_arc=n*(n-1)/2;
for(i=1;i<=max_arc;i++)
{
cout<<"\nEnter the edge "< cin>>origin>>destin;
if((origin==0)&&(destin==0))
break;
cout<<"\nEnter the weight for this arc:";
cin>>wt;
if(origin>n||destin>n||origin<=0||destin<=0)
{
cout<<"\nInvalid arcs";
i--;
}
else
{
adj[origin][destin]=wt;
adj[destin][origin]=wt;
}
}
if(i==0)
{
cout<<"\nSpanning tree not possible";
getch();
exit(0);
}
}
void graph::display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout< }
cout<<"\n";
}
}
int graph::allperm(class point state[MAX])
{
int i;
for(i=1;i<=n;i++)
{
if(state[i].status==TEMP)
return FALSE;
}
return TRUE;
}
int graph::maketree(class arc tree[MAX],int *weight)
{
class point state[MAX];
int i,min,count,current;
int u1,v1;
*weight=0;
for(i=1;i<=n;i++)
{
state[i].pre=0;
state[i].dist=infinity;
state[i].status=TEMP;
}
state[1].pre=0;
state[1].dist=0;
state[1].status=PERM;
current=1;
count=0;
while(allperm(state)!=TRUE)
{
for(i=1;i<=n;i++)
{
if(adj[current][i]>0 && state[i].status==TEMP)
{
if(adj[current][i] < state[i].dist)
{
state[i].pre=current;
state[i].dist=adj[current][i];
}
}

}
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status==TEMP && state[i].dist {
min=state[i].dist;
current=i;
}
}
state[current].status=PERM;
u1=state[current].pre;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
*weight=*weight+adj[u1][v1];
}
return count;
}
void main()
{
graph g;
int i,j;
int path[MAX];
int wttree,count;
class arc tree[MAX];
clrscr();
cout<<"\t\t"<<"PRIMS ALGORITHM";
g.creategraph();
cout<<"\nAdjacency Matrix:\n";
g.display();
count=g.maketree(tree,&wttree);
cout<<"\nWeight of spanningtree arc :"< cout<<"\nEdges to be included in the spanning tree arc:";
for(i=1;i<=count;i++)
{
cout<<"\n"< }
getch();
}




For Matrix formation please visit,

http://www.youtube.com/watch?v=sl6W3_Q4HZo

to watch the video.

Regards

Welcome to My world of Ideas Blog

Hi All,

Here you can post your ideas and thoughts and can share those things to your friends!!!