C语言中递归二进制搜索算法的分段错误

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?

这是一个带有递归二进制搜索算法的C程序，但是当我运行它时，调试器说二进制搜索功能中存在访问分段错误。为什么这样，我该如何解决这个问题？

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

谢谢：）

4 个解决方案

#1

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

您必须在val <...和val>之前检查low == high ...因为否则高可能会低于低，因此您的下一次递归可能会计算无效的mid

#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;
}

#3

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;    

}

#4

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

低 <高不保证。如果不是这种情况，你将要搜索数组绑定。< p>

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.

编辑：作为其他指出你也可以检查开头是否低==高但是不能确保函数的第一次调用具有声音值。

#1