-1

以下では、再帰関数を使用して単純な二分探索プログラムを作成しようとしています。実行すると、配列とキーを入力として検索する必要がありますが、その後コンパイラが突然停止します。どこかで無限ループが起きているのかもしれません。

#include<stdio.h>
int present_flag;
int binary_search(int array[],int low,int high,int key)
{
int mid=(high + low)/2;
if(low<=high)
{
    if (array[mid] == key)
    {
    printf("Key found at index %d \n",mid);
    return 1;
    }
        else if (array[mid] >key)
        return 0+binary_search(array,low,mid,key);
            else 
            return 0+binary_search(array,mid+1,high,key);;
}
else return 0;
}
main()
{
int array[9],i,n,key;
printf("Enter 9 numbers in asc order \n");
for(i=0;i<9;i++)
scanf("%d",&n);
printf("Enter number to be searched\n");
scanf("%d",&key);
present_flag=binary_search(array,0,8,key);
if (present_flag==0 )
printf("Number not present in array\n");
}
4

5 に答える 5

0

nitish712 の簡略化されたバージョンのコードに対応して、コードをさらに簡略化する別の方法は、単純に -1 を返し (要素が存在しない場合は 0 ではなく)、要素が存在する場合は mid 自体を返すことです。

int binary_search(int array[],int low,int high,int key)
{
int mid=(high + low)/2;
if (array[mid] == key)
{

    return mid;//This value can be utilized elsewhere in the code to check availability of the key in the array
}
if(low<high)
{
    if(array[mid] >key)
      return binary_search(array,low,mid,key);
    else 
      return binary_search(array,mid+1,high,key);
}
return -1;
}
于 2014-09-12T16:49:31.177 に答える
0

まず、compiler止められたのではありません。コンパイラは、プログラムを機械レベルの命令に変換するだけです。

次に、再帰呼び出しが停止しません。終了条件を正確に指定していないためです。したがって、あなたのプログラムはexecuting、スタックスペースがなくなるまで無期限でしたsegmentation fault.

修正されたコードは次のようになります (コメント プログラムで変更を指定しました)。

#include<stdio.h>
int present_flag;
int binary_search(int array[],int low,int high,int key)
{

if(low==high)//if boundaries are same, just compare with the value and return
             //appropriately...
{
    if(array[low]==key){
    printf("Key found at index %d \n",low);
    return 1;
}
else
return 0;
}
int mid=(high + low)/2;
if(low<high)
{
    if (array[mid] == key)
    {
    printf("Key found at index %d \n",mid);
    return 1;
    }
        else if (array[mid] >key)
        return binary_search(array,low,mid,key);//need not put a zero explicitly...
            else 
            return binary_search(array,mid+1,high,key);
}
else return 0;
}
main()
{
int array[9],i,n,key;
printf("Enter 9 numbers in asc order \n");
for(i=0;i<9;i++)
scanf("%d",&array[i]);// <--- this should be array[i] and not n. 
printf("Enter number to be searched\n");
scanf("%d",&key);
present_flag=binary_search(array,0,8,key);
if (present_flag==0 )
printf("Number not present in array\n");
}

関数をより単純な方法で書き直すと、次のようになります。

int binary_search(int array[],int low,int high,int key)
{
    int mid=(high + low)/2;
    if (array[mid] == key)
    {
        printf("Key found at index %d \n",mid);
        return 1;
    }
    if(low<high)
    {
        if(array[mid] >key)
          return binary_search(array,low,mid,key);
        else 
          return binary_search(array,mid+1,high,key);
    }
    return 0;
}
于 2013-10-19T18:29:30.003 に答える