Binary Search Using Recursive Function in C

Question

So I'm trying to write a binary search function that uses recursion and keep getting a segmentation fault if I go past two values in the array. I've looked at a bunch of other code doing what I'm trying to do and as far as I can see they appear to do the same thing. I'm a very novice programmer and feel like I'm banging my head against the wall with this. Any help would be appreciated.

int search(int value, int array[], int start, int end)
{
//Define new variables for use in recursion
int sizeArray, middleOfArray;
//Get size of array
sizeArray = (end - start) + 1;

//Find midpoint of array based off size
middleOfArray = sizeArray / 2;

//Base Case 1, if array unscannable, return -1
if (start > end) {
    return -1;
}

//Recursive Cases
else
{
    //If midpoint in array is > target value,
    //Search from beginning of array->one below midpoint
    if (array[middleOfArray] > value){
        return search(value, array, start, middleOfArray - 1);
    }
    //If midpoint in array is < target value,
    //search from one above midpoint->end of array
    else if (array[middleOfArray] < value) {
        return search(value, array, middleOfArray + 1, end);
    }
    //If none of the other cases are satisfied, value=midpoint
    //Return midpoint
    else {
        return middleOfArray;
    }
}
}

mostafaTmj · Accepted Answer · 2014-10-02 18:54:29Z

2

The problem is here:

middleOfArray = sizeArray / 2;

It should be like this:

middleOfArray = start + sizeArray / 2;

answered Oct 2, 2014 at 18:54

mostafaTmj

3934 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

syyc8A3QierDK4G Over a year ago

Thank you very much this makes the code work however I'm not sure I fully understand why. Do you mind elaborating a little? Thanks again

mostafaTmj Over a year ago

You're welcome! That's because you are using value of middleOfArray as start in recursions and it will change the start value in some recursions and your start won't be 0 after some call backs.

syyc8A3QierDK4G Over a year ago

Oh wow I see it now. I was thinking the array gets recreated, however the arrays size is the same, so you have to add back the middleOfArray to get into the correct array position. Yeesh that's rough. Thanks so much again I think I get it now.

Gaurav Parek · Accepted Answer · 2014-10-02 21:43:16Z

0

You can also get middle of array like this. Which will save you from one extra variable sizeofArray.

middleofArray=(start+end)/2;

answered Oct 2, 2014 at 21:43

Gaurav Parek

3276 silver badges22 bronze badges

Collectives™ on Stack Overflow

Binary Search Using Recursive Function in C

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related