c++ - 基于数组实现的递归搜索

Question

我在使用这个程序时遇到了一些问题，我不知道自己做错了什么；该程序应该是一个递归搜索程序，但是某些函数没有被正确调用(或根本没有)。问题似乎集中在“bin_search”部分，“int data [size]”部分再次弹出错误，提示“可变大小对象可能未初始化”。任何帮助将不胜感激。提前致谢!

# include <iostream> // Allows program to perform input and output
using std::cout; // program uses cout
using std::cin; // program uses cin



int bin_search ( int data[], int left, int right, int key, int NOT_FOUND)
{
 // calculate the index to search
 int index = ( ( ( key - data[ left ]) / ( data[ right ] - data[ left] ) )* (right - left)         ) + left;
 // terminating condition
 if ( data[index] == key )
 return key;
 // terminating condition
 if ( left >= right )
 return NOT_FOUND;
 // search recursively
 if ( key < data[index] )
 return bin_search ( data, left, index-1, key );
 else
 return bin_search ( data, index + 1, right, key );
}
    // end function bin search

int main()
{
 // function main begins program execution
  int size = 10;
  int bin;
  int data[size] = {0, 7, 12, 23, 44, 335, 426, 477, 658, 921};
  int key = 23;
 // let the user know about the program
 cout << "\n\n A program to search an element recursively.";
 // search and print the results to the user
 if ( bin_search( data, 0, size-1, key ) == key )
 cout << "\n\n\tThe key was found.";
 else
 cout << "\n\n\tThe key was not found.";
 // let the screen wait to see the output
 cout << "\n\n\t";
 system( "pause" );
 return 0; // indicate program executed successfully
 // end of function, main
}

Answer 1

一些注意事项:

1. 当有 n 个元素时，你想要有 n + 1 个位置!通过这种方式，您可以轻松处理空序列，并且如果未找到某些内容，则会返回一个明显的结果。
2. 定位要检查的索引 的计算非常复杂。您只想找到要搜索的序列的中间位置。 key 当然不是这个计算的一部分。
3. 需要处理序列为空的情况。
4. 就个人而言，我不会递归地实现二分搜索，尤其是如果调用不是尾递归的。
5. 在谈到个人喜好时，无论如何我都会用迭代器来实现它。