macOS Binary Search function problem in C++

[ingenious]

I'm using the Binary Search algorithm as a function in C++. I'm passing it an int array that I've read from a file, but something is happening in the meantime, since its values never reach the Binary Search function. Instead of four digit customer codes, I'm getting a list of zeros.

This int array works fine in the Bubble Sort function I'm also using.

Function prototype:

double TotalCharge (int, int);
void BubbleSort (int[], int [], double [], const int, string []);
int BinarySearch (int[], int, int, int);

Array Definitions:

const int max_num=100;
string Name[max_num];
int Usage[max_num], CustomerNumbers[max_num];
double AmountDue[max_num];

Here's the function call for Bubble Sort:

BubbleSort (Usage, CustomerNumbers, AmountDue, numcustomers, Name);

Here's the function call for Binary Search:

result=BinarySearch(CustomerNumbers, key, 0, max_num-1);

Here's my Bubble Sort function:

void BubbleSort (int a[], int b[], double c[], const int arraySize, string d[])
{
	int swap=1, Index, hold1, hold2;
	double hold3;
	string hold4;
	
	for (int pass = 0; swap==1; pass++) //passes
		{
			swap=0;
			for (Index = 0; Index < arraySize - 1 - pass; Index++) //one pass
				if (b [Index] > b[Index + 1])
					{
						 hold1=b[Index];
						 b[Index]=b[Index + 1];
						 b[Index + 1]=hold1;
						 swap=1;
						 
						 hold2=a[Index];
						 a[Index]=a[Index + 1];
						 a[Index + 1]=hold2;
						 swap=1;
						 
						 hold3=c[Index];
						 c[Index]=c[Index + 1];
						 c[Index + 1]=hold3;
						 swap=1;
						 
						 hold4=d[Index];
						 d[Index]=d[Index + 1];
						 d[Index + 1]=hold4;
						 swap=1;
					}
		}
}

Here's my Binary Search function:

int BinarySearch (int a[], int search_key, int low, int high)
{
	int middle;
	
	while (low <= high)
	{
		middle = (low+high)/2;
		
		if (search_key == a[middle]) //match
			return middle;
		else if (search_key < a[middle]) 
			high = middle-1; //search low end of array
		else
			low = middle+1;	//search high end of array
	}
	
	cout<<search_key <<endl;

	for (int b=0; b<=100; b++)
	{cout<<a[b]<<endl;}
	
	return -1; //key not found
}

I know this has to be something patently obvious, but for the life of me I can't figure it out. Why does it work for BubbleSort and not BinarySearch?

Any help is appreciated.

 

[toddburch]

Your search routine looks fine, and I tested it with some sample values, and had total success.

The problem must be elsewhere in your code. Sounds like a scope issue where you might be updating a copy of the array on the stack, and not the main array.

 

[ingenious]

Your search routine looks fine, and I tested it with some sample values, and had total success.

The problem must be elsewhere in your code. Sounds like a scope issue where you might be updating a copy of the array on the stack, and not the main array.

Thanks for the reply. I think the only time I'm editing that array is when I sort it with my BubbleSort function.

Would you mind compiling my program and seeing if you get the same results? Perhaps you'll see where the array has gone awry.

I'll PM it to you if you've the chance.

Thanks for your help.

 

[toddburch]

Sure, I can check it in the morning.

 

[ingenious]

email sent. PM'ing doesn't accept attachments.

never mind... here it is.

 

[toddburch]

Post data.txt dude.

 

[lee1210]

Always post a data file, i'm going to try to generate one myself... but an initial comment on style:

        for (Index = 0; Index < max_num; Index++)
        {AmountDue[Index]=0;}

That makes my eyes bleed. Again, since this is a style issue, there are options that are more readable. Here are two:

        for (Index = 0; Index < max_num; Index++) {
          AmountDue[Index]=0;
        }

        for (Index = 0; Index < max_num; Index++)
        {
          AmountDue[Index]=0;
        }

or even (though you'd have to change it if you needed more in the loop):

        for (Index = 0; Index < max_num; Index++) AmountDue[Index]=0;

I far prefer the first example. If there's no brace on the line with your control structure, you don't know if a block follows, a single expression, etc. If you see the brace right there, you know what's coming, and that there will be a matching brace (hopefully on its own line) that ends the control structure.

Again, this is a stylistic point, but it's never too early to learn to write readable code.

-Lee

Edit: Going through the code more, this was the ugliest piece I saw:

                if (kwh <= 300) charge=kwh*(.10);
                        else if (kwh > 300 && kwh <= 800) charge=(.09)*(kwh-300)+30;
                                else if (kwh > 800 && kwh <= 1300) charge=(.07)*(kwh-800)+75;
                                        else charge=(.055)*(kwh-1300)+110;

Indentation, in most cases, is used to indicate a new scope, i.e. a function, control block, etc. This waterfall of if-then-else is not terribly difficult to understand, but is an eyesore. Most people would be used to seeing something like that more like this:

                if (kwh <= 300) {
                  charge=kwh*(.10);
                } else if (kwh > 300 && kwh <= 800) {
                  charge=(.09)*(kwh-300)+30;
                } else if (kwh > 800 && kwh <= 1300) {
                  charge=(.07)*(kwh-800)+75;
                } else {
                  charge=(.055)*(kwh-1300)+110;
                }

 

[lee1210]

The error wasn't that serious. My major issues with the code is style at this point, but the error was in how you called your binary search function.

How you call it now would work if your array CustomerNumbers was FULL. The example file i wrote only had 4 entries. That meant there were a lot of 0s in the CustomerNumbers array. 0 is less than any 4 digit number. This breaks binary search because it depends on a sorted array. The array isn't completely sorted. You pass the number of records to BubbleSort, so it doesn't sort 1001 after all of the empty 0 entries. Your BinarySearch function already accepts a high value.

-Lee

P.S. This was the data i used, if someone else was to want to look at it:

1005 Test A
800
1008 Test B
720
1003 Test C
830
1001 Wog D
93

 

[ingenious]

Post data.txt dude.

yea, i'm the smart one.

sorry, by the time i posted this, i'd been staring at it for several hours and my brain was shot....


here goes:

 

[ingenious]

Always post a data file, i'm going to try to generate one myself... but an initial comment on style:

        for (Index = 0; Index < max_num; Index++)
        {AmountDue[Index]=0;}

That makes my eyes bleed. Again, since this is a style issue, there are options that are more readable. Here are two:

        for (Index = 0; Index < max_num; Index++) {
          AmountDue[Index]=0;
        }

        for (Index = 0; Index < max_num; Index++)
        {
          AmountDue[Index]=0;
        }

or even (though you'd have to change it if you needed more in the loop):

        for (Index = 0; Index < max_num; Index++) AmountDue[Index]=0;

I far prefer the first example. If there's no brace on the line with your control structure, you don't know if a block follows, a single expression, etc. If you see the brace right there, you know what's coming, and that there will be a matching brace (hopefully on its own line) that ends the control structure.

Again, this is a stylistic point, but it's never too early to learn to write readable code.

-Lee

Edit: Going through the code more, this was the ugliest piece I saw:

                if (kwh <= 300) charge=kwh*(.10);
                        else if (kwh > 300 && kwh <= 800) charge=(.09)*(kwh-300)+30;
                                else if (kwh > 800 && kwh <= 1300) charge=(.07)*(kwh-800)+75;
                                        else charge=(.055)*(kwh-1300)+110;

Indentation, in most cases, is used to indicate a new scope, i.e. a function, control block, etc. This waterfall of if-then-else is not terribly difficult to understand, but is an eyesore. Most people would be used to seeing something like that more like this:

                if (kwh <= 300) {
                  charge=kwh*(.10);
                } else if (kwh > 300 && kwh <= 800) {
                  charge=(.09)*(kwh-300)+30;
                } else if (kwh > 800 && kwh <= 1300) {
                  charge=(.07)*(kwh-800)+75;
                } else {
                  charge=(.055)*(kwh-1300)+110;
                }

thanks for the insight. i'm in an intro to c++ class, so I'm always learning

 

[lee1210]

So have you corrected the error?

-Lee

 

[ingenious]

So have you corrected the error?

-Lee

Yep- just found it. Instead of setting my high value to the highest subscript (max_num-1), I set it to the highest subscript with a value (numcustomers-1).

Thanks everyone for your help.

 

[toddburch]

Tapping fingers in desk... staring out window... wondering, hoping, Lee has fixed the bug... If not, then we'll pull out the big guns. (yeah right).

EDIT - good deal. Now on to other things.