having problem in binary search

March 24, 2010 at 22:01:06
Specs: Windows XP
i am having the problem with the beg point and end point index number in the following program:
/*Binary Search*/
#include<stdio.h>
#include<conio.h>

main()
{
	int data[13] = {11,21,36,46,52,55,67,75,79,81,86,97,99};
	int LB,UB,ITEM,LOC,MID;

	LB = 0;
	UB = 12;
	MID = ((LB+UB)/2);
	clrscr();
	printf("%d",&MID);
	printf("\nEnter the number to be searched: ");
	scanf("%d",&ITEM);

	do
	{
		if(data[MID] == ITEM)
		{       LOC = MID;
			printf("\nposition : %d",LOC);
		}
		else
		{
			if(data[MID]<ITEM)
			{
				LB=MID;
				MID=(LB+UB)/2;
			}
			if(data[MID]>ITEM)
			{
				UB = MID;
				MID = (LB+UB)/2;
			}
			LOC = MID;
		}
	} while(LB<=UB && data[MID]!=ITEM);

	printf("\nThe position : %d",&LOC);

the MID value is reflected as -16
whwereas it should be 6
PLEASE HELP


See More: having problem in binary search

Report •


#1
March 24, 2010 at 22:29:59
I tried while loop also but not able to make it work
this time MID value and LB and UB did well but i dont know why line 38 is showing "position : -26"


#include<stdio.h>
main()
{
	int data[5]={3,4,5,6,7};

	int MID,LB,UB,ITEM,LOC=0;
	LB = 0;
	UB = 4;
	MID = (LB+UB)/2;
	printf("MID : %d",MID);

	printf("\nEnter the ITEM");
	scanf("%d",&ITEM);

	printf("\nITEM : %d",ITEM);

	while(LB<UB && data[MID]!=ITEM)
	{
		if(data[MID] == ITEM)
		{       LOC = MID;
			printf("\nposition : %d",LOC);
		}
		else
		{
			if(data[MID]<ITEM)
			{
				LB=MID;
				MID=(LB+UB)/2;break;
			}
			if(data[MID]>ITEM)
			{
				UB = MID;
				MID = (LB+UB)/2;break;
			}
		}
	}

	printf("\nThe position : %d",&LOC);
}

PLEASE HELP


Report •

#2
March 24, 2010 at 22:32:49
Just pass the ints to printf rather than their pointer. Its casting the pointer to an int when you want the value of the ints.

.....
	printf("MID : %d",MID);
.....
	printf("\nThe position : %d",LOC);

Also if a number not in the data array is used the code goes into a infinite loop.

Edit: You beat me to it with "MID" but "LOC" is still being passed as a pointer.

I also copied the wrong example...


Report •

#3
March 24, 2010 at 22:45:59
Sorry Mr.Judago but i didnt get u...........please be simple in language my english is not so good.....

Report •

Related Solutions

#4
March 24, 2010 at 22:46:47
Looking into it further "UB" should be set to the number of items in the array, not the highest index.

Therefore it should be:

UB = 13;

For the original post.


Report •

#5
March 24, 2010 at 22:51:14
You beat me to posting again!

Simply put &MID and &LOC are pointers to ints. They are memory locations not the value stored in memory.

I only skimmed over it but here are the changes I made to the original:

/*Binary Search*/
#include<stdio.h>
#include<conio.h>
main()
{
	int data[13] = {11,21,36,46,52,55,67,75,79,81,86,97,99};
	int LB,UB,ITEM,LOC,MID;

	LB = 0;
	UB = 13;
	MID = ((LB+UB)/2);
	clrscr();
	printf("%d",MID);
	printf("\nEnter the number to be searched: ");
	scanf("%d",&ITEM);
	printf("%d",ITEM);
	do
	{
		if(data[MID] == ITEM)
		{       LOC = MID;
			printf("\nposition : %d",LOC);
		}
		else
		{
			if(data[MID]<ITEM)
			{
				LB=MID;
				MID=(LB+UB)/2;
			}
			if(data[MID]>ITEM)
			{
				UB = MID;
				MID = (LB+UB)/2;
			}
			LOC = MID;
		}
	} while(LB<=UB && data[MID]!=ITEM);

	printf("\nThe position : %d",LOC);
} 


Report •

#6
March 24, 2010 at 22:58:17
Thank u very much Mr.Judago
i was stuck with this code fron past 2 days
since i m doing BCA from correspondence and there is no body to guide me
thank you again

Report •

#7
March 24, 2010 at 23:05:48
No problem.

Be warned it will still go in an infinite loop if a number not in "data[x]" is entered.


Report •

#8
March 24, 2010 at 23:35:03
This is working fine now-----------

/*Binary Search*/
#include<stdio.h>
#include<conio.h>

main()
{
	int data[13] = {11,21,36,46,52,55,67,75,79,81,86,97};
	int LB,UB,ITEM,LOC,MID;

	LB = 0;
	UB = 12;
	MID = (LB+UB)/2;
	clrscr();
	printf("%d",MID);
	printf("\nEnter the number to be searched: ");
	scanf("%d",&ITEM);

	do
	{
		if(data[MID] == ITEM)
		{       LOC = MID;
			printf("\nposition : %d",LOC);
		}
		else
		{
			if(data[MID]<ITEM)
			{
				LB=MID;
				MID=(LB+UB)/2;
			}
			if(data[MID]>ITEM)
			{
				UB = MID;
				MID = (LB+UB)/2;
			}
			if(LB+1==UB)
			{
				printf("Number not int the list");
				break;
			}
			LOC = MID;
		}
	} while(LB<=UB && data[MID]!=ITEM);

	printf("\nThe position : %d",LOC);
}

THANK U


Report •


Ask Question