c - 为什么不使用递归进行二分查找排序数组

Question

我正在尝试实现一个二分搜索，其中 n 是我的数组的大小，并且它不适用于递归，只有当我不使用递归时它才起作用，我似乎不明白为什么

int mid = 0;
int low = 0;

bool search(int value, int values[], int n)
{
   do
   {
   mid = (low + n)/2; 
   if(values[mid] == value) 
   {
        return true;
   }
   else if (values[mid]>value) 
   {
       n= mid -1;
       return search(value, values,  n);


   }
   else if (values[mid]<value)
   {
        low = mid + 1;
       return search(value, values,  low);

   }
 }
 while (n > low);

return false;
}

Answer 1

问题是您调用递归调用来搜索数组的上半部分，并使用指向下半部分的指针。所以如果该值在上半部分，它就不会找到它。你需要这样的东西:

bool search(int value, int values[], int n) {
    int mid = n/2;
    if (n <= 0) {
        return false;
    } else if (values[mid] == value) {
        return true;
    } else if (values[mid] > value) {
        return search(value, values, mid);
    } else if (values[mid] < value) {
        return search(value, values + mid + 1, n - mid - 1);
    }
 }