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%，并且您传递的指针错误(您应该传递数组的第二个“一半”)。 p>

在这两种情况下，“数组”的大小始终是函数接收到的大小的一半。在第二种情况下，您需要传递一个指向数组后半部分的指针。

有点像

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

---

您还错误地处理了函数的返回值。它不是一个值，它是一个指向该值的指针，您需要这样对待它。并且可以从另一个(相关)指针中减去一个指针，这称为指针算术。