Binary Search function problem in C++

Discussion in 'Mac Programming' started by ingenious, Dec 10, 2008.

  1. ingenious macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #1
    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:
    Code:
    double TotalCharge (int, int);
    void BubbleSort (int[], int [], double [], const int, string []);
    int BinarySearch (int[], int, int, int);
    Array Definitions:
    Code:
    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:
    Code:
    BubbleSort (Usage, CustomerNumbers, AmountDue, numcustomers, Name);
    Here's the function call for Binary Search:
    Code:
    result=BinarySearch(CustomerNumbers, key, 0, max_num-1);
    Here's my Bubble Sort function:
    Code:
    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:
    Code:
    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.
     
  2. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #2
    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.
     
  3. ingenious thread starter macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #3
    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.
     
  4. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
  5. ingenious thread starter macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #5
    email sent. PM'ing doesn't accept attachments.

    never mind... here it is.
     

    Attached Files:

  6. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
  7. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #7
    Always post a data file, i'm going to try to generate one myself... but an initial comment on style:
    Code:
            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:
    Code:
            for (Index = 0; Index < max_num; Index++) {
              AmountDue[Index]=0;
            }
    
    Code:
            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):
    Code:
            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:
    Code:
                    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:
    Code:
                    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;
                    }
    
     
  8. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #8
    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:
    Code:
    1005 Test A
    800
    1008 Test B
    720
    1003 Test C
    830
    1001 Wog D
    93
    
     
  9. ingenious thread starter macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #9
    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:
     

    Attached Files:

    • data.txt
      File size:
      388 bytes
      Views:
      45
  10. ingenious thread starter macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #10

    thanks for the insight. i'm in an intro to c++ class, so I'm always learning :)
     
  11. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
  12. ingenious thread starter macrumors 68000

    ingenious

    Joined:
    Jan 13, 2004
    Location:
    Washington, D.C.
    #12
    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.
     
  13. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #13
    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.
     

Share This Page