C:递归函数 - 二进制搜索

Question

我正在尝试构建一个递归函数,它通过与中间值进行比较并根据相对大小继续返回已排序数组中的地址.如果值不在数组中,则应该只打印NULL.现在函数的第一部分工作,但是每当发生null时我都会遇到分段错误.代码如下:

#include <stdio.h> 

int *BinSearchRec(int arr[], int size, int n){
  if(n==arr[size/2]){
    return &arr[size/2];
  } 

  else if(n>arr[size/2]) {
    return(BinSearchRec(arr, size+size/2, n));
  }

  else if(n<arr[size/2]) {
    return(BinSearchRec(arr, size-size/2, n));
  }

  else{
    return NULL;                    
  }
 }

 main(){
    int numb[]={2,7,8,9};

 if((int)(BinSearchRec(numb, 4, 22)-numb)>=0)   {
    printf("Position: %d \n", (int)(BinSearchRec(numb, 4, 22)-numb)+1);
    }

     else{
       printf("NULL \n");
     }

  }

Answer 1

你的递归调用是错误的.在第一种情况下,您声称数组的大小比原来大 50%,并且您传递指针错误(您应该传递数组的第二个"一半").

在这两种情况下,"数组"的大小始终是函数接收的一半.在第二种情况下,您需要将指针传递给数组的后半部分.

就像是

else if(n>arr[size/2]) {
  return(BinSearchRec(arr + sizeof/2, size/2, n));
}

else if(n<arr[size/2]) {
  return(BinSearchRec(arr, size/2, n));
}

您还要将函数的返回值视为错误.它不是一个值,它是指向值的指针,您需要将其视为这样.从另一个(相关的)指针中减去一个指针是可以的,它叫做指针算术.