c++ - 使用迭代和递归的二进制搜索算法

Question

我正在寻找排序数组中的元素 x。它比较 xx 或数组范围等于零 我在出错的地方遇到段错误 我找不到我的代码在下面我正在 gcc 编译器中编译。

#include <iostream>
using namespace std;

// iterative
int bsearch(int a[], int sz, int x)
{
  int low = 0;
  int high = sz -1;

  while(low <= high) {
    int mid = (low+high)/2;

    if(x < a[mid]) 
      high = mid - 1;
    else if(x > a[mid]) 
      low = mid + 1;
    else 
      return a[mid];
  }
  return -1;
}

// recursive
int bsearch_recursive(int a[], int low, int high, int x)
{
  if(low > high) return -1;

  int mid = (low + high)/2;

  if(x < a[mid])
    bsearch_recursive(a, low, mid-1, x);
  else if(x > a[mid])
    bsearch_recursive(a, mid+1, high, x);
  else
    return a[mid];
}

void print(int n)
{
  if(n == -1) {
    cout << "not found" << endl;
  return;
  }
  cout << "found" << endl;

}
int main()
{        
  int a[]={3, 7, 9, 16, 23, 34, 67, 87, 92};
  int arraySize = sizeof(a)/sizeof(int);
  int result;

  result = bsearch(a, arraySize, 7); 
  print(result);
  result = bsearch(a, arraySize, 92); 
  print(result);
  result = bsearch(a, arraySize, 77); 
  print(result);

  result = bsearch_recursive(a, 0, arraySize-1, 7); 
  print(result);
  result = bsearch_recursive(a, 0, arraySize-1, 92); 
  print(result);
  result = bsearch_recursive(a, 0, arraySize-1, 77); 
  print(result);

  return 0;
}

Answer 1

您的递归搜索需要每个路径都有返回值，否则其结果是不确定的。

递归函数的工作方式与其他函数完全一样——如果它声称要返回一个值，它就必须这样做。它不仅会自动返回终止递归调用的结果。

int bsearch_recursive(int a[], int low, int high, int x)
{
    if(low > high) return -1;

    int mid = (low + high)/2;
    if(x < a[mid])
        return bsearch_recursive(a, low, mid-1, x);
    else if(x > a[mid])
        return bsearch_recursive(a, mid+1, high, x);
    else
        return a[mid];
}

你的编译器应该警告过你——如果没有，打开更多警告。
如果确实如此，而您不在乎，请开始听取警告。