Thread: Binary Search Help!

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    44

    Binary Search Help!

    Hi people. Been doing some revision for an exam I have in a few months. To get a better idea i've been coding some search and sort algorithms. I have stumbled across a bug with my binary search and can't find it for the life of me! Could be trivial, but I would much appreciate some help. =]

    Any questions about the code please don't hesistate to ask. Should take some input like '1234567' then say ask it to search for '5'. It should return a value of '4' as this is the index of its point in the array.

    Thanks.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    char search(  char *A, int min, int max, int val )
    {
    	int mid = ( min + max ) / 2  ;
    
    	if( min > max )							/* NOT FOUND */
    		return -1 ;
    	if( A[mid] == val )						/* FOUND  */
    		return mid ;
    	if( A[mid] < val )
    		search( A, ( mid + 1 ), max, val ) ;
    	if( A[mid] > val )
    		search( A, min, ( mid - 1 ), val ) ;
    }
    
    int main( void )
    {
    	int z, max, min, val, index  ;
    	int i = 0 ; 
    	char A[100] ;
    	char *B ;
    	
    	printf( "BINARY SEARCH ALGORITHM\n" ) ;
    	printf( "Worst Case: O(logn)	Best Case: O(1)\n" ) ;
    	printf( "Enter numbers to be searched\n" ) ;
    	
    	while(   ( z = getchar() ) != '\n'  ) 
    	{
    		A[i] = z  ;
    		i++ ;
    	}
    	
    	min = 0 ;
    	max = i - 1  ;
    	i = 0 ;
    	B= calloc( max, sizeof( int ) ) ;
    	
    	while( max >= i )  
    	{
    		B[i] = A[i] ;
    		i++ ;
    	}
    	
    	printf( "What number would you like to find?\n" ) ;
    	scanf( "%d", &val ) ;
    	/* changes input value to ascii , to work with the  values in the array in the search function */
    	val = val + 48 ;
    	index = search( B, min, max , val )  ;
    	printf( "Number is at index number %d\n", index ) ;
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by killpoppop View Post
    I have stumbled across a bug with my binary search and can't find it for the life of me! Could be trivial, but I would much appreciate some help. =]
    Very mysterious! Why do you think there is a bug if you can't find it?

    Sorry, I'm being facetious. What I meant is, why don't you explain the problem a little further, rather than presuming someone else is going to compile and run tests on this code when you already have that information but could not be bothered to include it in your post...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    Sorry =]

    Right everything goes in fine into the search function. That is the array of numbers, the lowest index of the array '0', the highest index of the array and the value im trying to find in the original array. As far as I can see the search function is fine. And if you ask it to find the number in the middle of the array it does it fine. But search for any other number in the array and it returns the number '32'. I can't see where I've gone wrong. Hopefull someone else will!

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    search() is potentially recursive. So one step in potentially the right direction would be to have it return a value recursively.
    Code:
    	if( A[mid] < val )
    		search( A, ( mid + 1 ), max, val ) ; /* wrong */
                    return search( A, ( mid + 1 ), max, val ) ; /* ahhh... */
    Otherwise, those "recursive" calls are pointless, and the original call to the function does not return anything, thus the value of index will be undefined/anything.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    Yep. Nailed it. Thank you so much, can't believe I didn't think of that. Spent ages isolating the problem to those lines! But makes perfect sense, without the return the recursive calls do nothing. Thanks again! =]

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    Moved straight on to the next sort. Tried to put together a merge sort. Got the merge function working well, but once again its not recursive. So given the input '4' '3' '2' '1'. It splits it in two arrays '43' and '21'. Then sorts giving '2143'. I need it to slice up the array once more and sort. So '43' goes to '4' and '3' which is sorted to '34' and the same for '21' to '12'. I don't believe there are any issues with the code only just the fact I can't work out how to make it recursive.

    Code:
    #include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    int partition( int *A, int min, int max )
    {
    	int mid;
    	if ( max > min)
    	{
    		mid = ( max + min ) / 2 ;
    		partition( A,  min, mid ) ;
    		partition( A, mid + 1 , max ) ;
    		merge( ( A + min ), ( A + min + mid ), mid, mid ) ;
    	}
    }
    
    
    int merge( int *A, int *B, int na, int nb )
    {
    	int *C	= (int *)malloc( ( na + nb ) * sizeof( int ) ) ;
    	int i = 0, j = 0, k = 0 ;
    	
    	while (i < na && j < nb)
    	{
    		if( A[i] < B[j] )
    		{
    			C[k] = A[i] ;
    			i++ ;
    		}
    		else
    		{
    			C[k] = B[j] ;
    			j++ ;
    		}
    		k++ ;
    	}
    	`
    	while ( i < na )
    	{
    		C[k] = A[i] ;
    		k++ ;
    		i++ ;
    	}
     
    	while ( j < nb )
    	{
    		C[k] = B[j] ;
    		k++ ;
    		j++ ;
    	}
    	
    	/* Tests that what is in the final array is correct */
    	printf( "%d", C[0] ) ;
    	printf( "%d", C[1] ) ;
    	printf( "%d", C[2] ) ;
    	printf( "%d", C[3] ) ;
    	//printf( "%d", C[4] ) ;
    	//printf( "%d", C[5] ) ;
    	//printf( "%d", C[6] ) ;
    	//printf( "%d\n", C[7] ) ; 
    	
    }
     
    int main( void )
    {
    	int i = 0 , min = 0 ;
    	int A[8] ;
    	int  B[4] = { 5, 4, 2, 7 } ;
    	int C[4] = { 3, 6, 1, 8 } ;
    	
    	printf( "MERGE SORT ALGORITHM\n" ) ;
    	printf( "Worst Case: O(nlogn)	Best Case: O(n)\n" ) ;
    	printf( "Enter numbers to be sorted:\n" ) ;
    	
    	while( i < 4 )
    	{
    		scanf( "%d", &A[i] ) ;
    		//printf( "%d\n", A[i] ) ;
    		i++ ;
    	}
    	
    	/* To test the merge function works correctly */
    	//merge( B, C, 4, 4 ) ;
    	
    	partition( A, min, i ) ;
    }

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Your code is actually close than you think to being done. It is recursive already. I would just rename 'partition' to 'mergeSort'.
    Part of what's tripping you up is that you need to come up with a consistent strategy for dealing with the ends of a range of items.
    Your initial call to partition uses min as the first item and max as referring to one past the last item (same as the count). This is a good strategy to use! It's the same on the SC++L uses.

    Noting that, here are some places you've tripped up:
    Code:
    		partition( A,  min, mid ) ;
    		partition( A, mid + 1 , max ) ;
    Note that what you've picked for mid here is used as the "one past the last item" in the first call, and that means that the same item (not plus 1) should be used as the start of the other partition.

    Code:
    	if ( max > min)
    This recusrion temination condition isn't right. What if you only have one item? min is zero and max is one. Should the if-statement really be entered when there is only one item? Nope.

    Code:
    		merge( ( A + min ), ( A + min + mid ), mid, mid ) ;
    You're forgetting that min is not always zero on recursive calls here. You don't need to add A+min+mid here. The second partition starts at just A+mid.
    Also, both portion sizes are wrong. The first one will be of size (mid-min) and the second one is of (max-mid). (Then it'll work for arrays that are not exactly a power of two number of items as well)

    Walk through one iteration of that function using values for min and max such as 4 and 9 (which actually occurs on a recursive call of sorting 9 items) and you'll see how the above changes make it right.

    Once 'merge' has copied everything across into C, you need to copy it all straight back into A.

    After all that you're basically done.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    First of all thanks a lot for the great reply, thought i'd try and tackle it now rather than in the morning! Made all the changers. Points 2 and 3 make perfect sense to me, a little unsure about 1 but i believe its right. However i'm not getting a print out anymore?

    Quote Originally Posted by iMalc View Post
    Noting that, here are some places you've tripped up:
    Code:
    		partition( A,  min, mid ) ;
    		partition( A, mid + 1 , max ) ;
    Note that what you've picked for mid here is used as the "one past the last item" in the first call, and that means that the same item (not plus 1) should be used as the start of the other partition.
    First issue:
    Code:
                 partition( A, min, mid ) ;
                partition( A, mid, max ) ;
    Quote Originally Posted by iMalc View Post
    Code:
    	if ( max > min)
    This recusrion temination condition isn't right. What if you only have one item? min is zero and max is one. Should the if-statement really be entered when there is only one item? Nope.
    Second issue:
    Code:
     if ( max > 1 )
    Quote Originally Posted by iMalc View Post
    Code:
    		merge( ( A + min ), ( A + min + mid ), mid, mid ) ;
    You're forgetting that min is not always zero on recursive calls here. You don't need to add A+min+mid here. The second partition starts at just A+mid.
    Also, both portion sizes are wrong. The first one will be of size (mid-min) and the second one is of (max-mid). (Then it'll work for arrays that are not exactly a power of two number of items as well)
    Third issue:
    Code:
     merge( ( A + min ), ( A + mid ), ( mid - min ), ( max -mid ) )

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by killpoppop View Post
    Second issue:
    Code:
     if ( max > 1 )
    Almost! You got the rest of them right, but this one should be (max-min > 1)

    Want to post the updated code?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    Ahh yes, makes sense. Thanks =]

    Code:
    #include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    int mergeSort( int *A, int min, int max )
    {
    	int mid;
    	if ( ( max - min ) > 1 )
    	{
    		mid = ( max + min ) / 2 ;
    		mergeSort( A,  min, mid  ) ;
    		mergeSort( A, mid, max ) ;
    		merge( ( A + min ), ( A + mid ), ( mid - min ), ( max - mid ) ) ;
    	}
    }
    
    
    int merge( int *A, int *B, int na, int nb )
    {
    	int *C	= (int *)malloc( ( na + nb ) * sizeof( int ) ) ;
    	int i = 0, j = 0, k = 0 ;
    	
    	while (i < na && j < nb)
    	{
    		if( A[i] < B[j] )
    		{
    			C[k] = A[i] ;
    			i++ ;
    		}
    		else
    		{
    			C[k] = B[j] ;
    			j++ ;
    		}
    		k++ ;
    	}
    	
    	while ( i < na )
    	{
    		C[k] = A[i] ;
    		k++ ;
    		i++ ;
    	}
     
    	while ( j < nb )
    	{
    		C[k] = B[j] ;
    		k++ ;
    		j++ ;
    	}
    		
    	printf( "%d", C[0] ) ;
    	printf( "%d", C[1] ) ;
    	printf( "%d", C[2] ) ;
    	printf( "%d", C[3] ) ;
    	//printf( "%d", C[4] ) ;
    	//printf( "%d", C[5] ) ;
    	//printf( "%d", C[6] ) ;
    	//printf( "%d\n", C[7] ) ; 
    	
    }
     
    int main( void )
    {
    	int i = 0 , min = 0 ;
    	int A[8] ;
    	int  B[4] = { 5, 4, 2, 7 } ;
    	int C[4] = { 3, 6, 1, 8 } ;
    	
    	printf( "MERGE SORT ALGORITHM\n" ) ;
    	printf( "Worst Case: O(nlogn)	Best Case: O(n)\n" ) ;
    	printf( "Enter numbers to be sorted:\n" ) ;
    	
    	while( i < 4 )
    	{
    		scanf( "%d", &A[i] ) ;
    		//printf( "%d\n", A[i] ) ;
    		i++ ;
    	}
    	
    	/* To test the merge function works correctly */
    	//merge( B, C, 4, 4 ) ;
    	
    	mergeSort( A, min, i ) ;
    }

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Cool. You've done pretty well if you ask me. Only thing left is to copy the contents of C back into A, and to free C:
    Code:
    for (int i=0; i<na + nb; i++)
    {
        A[i] = C[i];
    }
    free(C);
    This works because we happen to know that B follows immediately after A, given how merge is called. (If anything else called it differently then it wouldn't work)
    Try printing out the entire 'A' array after calling mergeSort and it should be sorted now.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    Works perfectly thank you! Just one more little question to do with the print out of A.

    Sample Input:
    4
    3
    2
    1
    Sample Output:
    1st Line: 3421 Still dont get how its sorted this. It's split it into 2 arrays of size 2. So then you have two piles. 43 and 21. And if you sort this surely you end up with 2143? But it seems its only sorted the first array of size 2. But from what I remember the sort splits it all the way down to arrays of size one before it starts to merge them back again.

    2nd Line: 1220092882584200288 What does all this mean? =]
    3rd Line: 1234 This is want we want to see!


    I could be talking rubbish, but the idea of me doing this is to get a full understanding of the sort so any answers would be great!

    Thanks again.

  13. #13
    Registered User
    Join Date
    Nov 2008
    Posts
    44
    On playing around with the code it now seems to make more sense.

    Code:
    	for ( l=0; l < na + nb ; l++)
    	{
    	A[l] = C[l] ;
    	printf ( "%d ", A[l] ) ;
    	}
    	free(C) ;
    	printf( "\n" ) ;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM