# Thread: Recursive Binary Search

1. ## Recursive Binary Search

Hey, guys. I'm having trouble with creating a code for a recursive binary search. Whenever I run the code, it says "Segmentation fault (core dumped)". What should I change in my code? Here it is:

Code:
```while(lower<=upper){
input2(&search);
if(search==-1)
printf("break;");
printf("Found %d at index %d", search, binary(array, n, search, lower, upper));
}

int binary(int array, int n, int search, int lower, int upper){

int middle;
lower=0;
upper=n-1;

middle=(lower+upper)/2;

if (array[middle] > search) // key is in lower subset
return binary(array, n, search, lower, middle-1);
else if (array[middle] < search) // key is in upper subset
return binary(array, n, search, middle+1, upper);
else // key has been found
return middle;
}```

2. Tidying up the formatting:
Code:
```int binary(int array, int n, int search, int lower, int upper){
int middle;
lower=0;
upper=n-1;
middle=(lower+upper)/2;

if (array[middle] > search) // key is in lower subset
return binary(array, n, search, lower, middle-1);
else if (array[middle] < search) // key is in upper subset
return binary(array, n, search, middle+1, upper);
else // key has been found
return middle;
}```
If you ignore the value of upper that was passed in and set upper to n-1 every time (where n never changes), why bother passing in upper at all?
Hint: You don't need n.

Then consider what happens when you search for a value that is not in the array, or more specifically, a value that is either lower than all values in the array, or greater than all values in the array.

3. Correct me if I am wrong but these are the things you might want to consider.

1) Try passing the Pointer to the Array instead of the Array itself. Its expensive if you pass the whole array all the time.

2)Like iMalc Said, You didnt consider the case where the item to be searched is not in the list. In the current condition of your code. If the Input Array is (1,2,3,4,5) and you want to search 7 in it. You will be facing an Infinite loop. You just need to check if Upper not equal Lower in the if conditions, containing the recursive calls.

Other than that its awsome. Good Luck.

4. Originally Posted by sunny`
1) Try passing the Pointer to the Array instead of the Array itself. Its expensive if you pass the whole array all the time.
He is already passing a pointer to the array but the function doesn't accept one:
Code:
`int binary(int array, int n, int search, int lower, int upper)`
What type is array? Can you index it?

A better compiler would have told Tim.

Bye, Andreas

5. ^^^ Should be getting an error, or at least a warning, out of the int array parameter.

Sunny, in C, you always are passing just a pointer to the array (in the form of the array name itself). Never the whole array.

6. Totally missed that array was not a pointer. Given he got a core dump, it obviously compiled at some point. But without a pointer there it certainly wont compile. Darn contradictory information!

Popular pages Recent additions