c - C の再帰的二分探索アルゴリズムのセグメンテーション違反

Question

これは、再帰的二分探索アルゴリズムを使用した C プログラムですが、実行すると、二分探索関数にアクセス セグメンテーション違反があるとデバッガーに表示されます。これはなぜですか、どうすれば修正できますか?

再帰的二分探索関数は次のとおりです。

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

ありがとうございました ：）

Answer 1

エッジケースはオフです。具体的には、lowとインデックスが合格すると、テストhighに到達する前に再帰的に呼び出し続けます。low == highテストを並べ替えます。

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

Answer 2

これを試して：

コード内の if 構造を修正

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;    

}

Answer 3

low<high確実ではありません。そうでない場合は、バインドされた配列から検索します。

そのための健全性チェックを追加します。

if (low < high)
     return -1;

EDIT：他の指摘として、最初に low == high かどうかを確認することもできますが、関数の最初の呼び出しに適切な値があることを保証するものではありません。