current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

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 :)

share|improve this question
1  
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 Jul 24 '13 at 9:40
    
How do you call the function? Where is the crash (at which line)? Can you please show the debugger backtrace? –  Joachim Pileborg Jul 24 '13 at 9:40
3  
You do not ensure that low is actually lower than hight. Add a test for that. –  mathk Jul 24 '13 at 9:42
    
@KarthikT Thanks so much, this made it work :) –  Michael Ferashire Silva Jul 24 '13 at 9:44
1  
@MichaelFerashireSilva Great! you are most welcome! –  Karthik T Jul 25 '13 at 2:26

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
    
thanks very much :) –  Michael Ferashire Silva Jul 24 '13 at 9:46
    
what if low > high at the first place –  mathk Jul 24 '13 at 9:51
    
@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. –  Ingo Leonhardt Jul 24 '13 at 10:15
    
this is basic security check. Never trust the input. –  mathk Jul 24 '13 at 13:48
up vote 2 down vote

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;
}
share|improve this answer
    
yes I realized that I was wrong :( –  Grijesh Chauhan Jul 24 '13 at 10:08
up vote 0 down vote

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;    

}
share|improve this answer
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.