Segmentation fault in recursive Binary Search Algorithm in C

Question

This is a C program with the recursive binary search algorithm, however when I run it, the debugger says there is an access segmentation fault in the binary search function. Why is this and how do I fix this?

Here is the recursive binary search function:

int binSearch(int val, int numbers[], int low, int high)                 
{
     int mid;

     mid=(low+high)/2;
     if(val==numbers[mid])
     {  
                return(mid);          
     }   
     else if(val<numbers[mid])
     {
                return(binSearch(val, numbers, low, mid-1));               
     }            
     else if(val>numbers[mid])
     { 
                return(binSearch(val, numbers, mid+1, high));  
     }    
     else if(low==high)
     {
                return(-1);    
     }
}

Thank you :)

Do you know where exactly it is seqfaulting? Can you try to move the last condition to the top of the function and see if it fixes it? — Karthik T
– Karthik T, Commented Jul 24, 2013 at 9:40
How do you call the function? Where is the crash (at which line)? Can you please show the debugger backtrace? — Some programmer dude
– Some programmer dude, Commented Jul 24, 2013 at 9:40
You do not ensure that low is actually lower than hight. Add a test for that. — mathk
– mathk, Commented Jul 24, 2013 at 9:42

Ingo Leonhardt · Accepted Answer · 2013-07-24 09:44:30Z

5

You must check low == high before val < ... and val > ... because otherwise high could become less than low and so your next recursion might calculate an invalid mid

answered Jul 24, 2013 at 9:44

Ingo Leonhardt

9,9392 gold badges26 silver badges37 bronze badges

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

3 Comments

mathk Over a year ago

what if low > high at the first place

Ingo Leonhardt Over a year ago

@mathk I would call that an invalid call to binSearch() so it should be enough to require low <= high in the function's doc. But of course you could check it first if you preferred.

mathk Over a year ago

this is basic security check. Never trust the input.

Grijesh Chauhan · Accepted Answer · 2013-07-24 10:06:59Z

2

Your edge cases are off: specifically, when your low and high indices pass, you continue to call recursively before you reach the low == high test. Rearrange the tests:

int binSearch(int val, int numbers[], int low, int high) {
    int mid = (low + high) / 2;

    if (val == numbers[mid]) return mid;

    if (val < numbers[mid]) {
        if (mid > low) return binSearch(val, numbers, low, mid-1);
    } else if (val > numbers[mid]) {
        if (mid < high) return binSearch(val, numbers, mid+1, high);
    }
    return -1;
}

edited Jul 24, 2013 at 10:06

Grijesh Chauhan

58.6k20 gold badges145 silver badges214 bronze badges

answered Jul 24, 2013 at 9:49

Lee Daniel Crocker

13.3k4 gold badges33 silver badges56 bronze badges

Comments

P0W · Accepted Answer · 2013-07-24 09:48:10Z

0

Try this:

Fixed if constructs in your code

int binSearch(int val, int numbers[], int low, int high)                 
{
     int mid;

     mid=(low+high)/2;

     if(low<=high)
     {
         if(val==numbers[mid])
           return mid;          

         else if(val<numbers[mid])
           return binSearch(val, numbers, low, mid-1);

        else 
          return binSearch(val, numbers, mid+1, high);  
     }
     else
           return -1;    

}

answered Jul 24, 2013 at 9:48

P0W

48.1k9 gold badges79 silver badges124 bronze badges

Comments

mathk · Accepted Answer · 2013-07-24 09:48:40Z

0

low < high is not ensure. If that is not the case your are going to search out of the array bound.

Add a sanity check for that.

if (low < high)
     return -1;

EDIT: as other point out you can also check if low == high at the beginning but that does not ensure that the first call of the function have sound value.

answered Jul 24, 2013 at 9:48

mathk

8,1416 gold badges47 silver badges76 bronze badges

1 Comment

Muhammad Fouad Alharoon Over a year ago

Normally, the low index shall be less than the high index, so what is the case to be covered by this condition?!

Collectives™ on Stack Overflow

Segmentation fault in recursive Binary Search Algorithm in C

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related