1. ## 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  ;

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. Originally Posted by killpoppop
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...

3. 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. 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.

5. 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. 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. 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.

8. 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?

Originally Posted by iMalc
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 ) ;```
Originally Posted by iMalc
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 )`
Originally Posted by iMalc
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. Originally Posted by killpoppop
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?

10. 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. 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.

12. 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. 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" ) ;```