-2

我正在编写一个递归二进制搜索程序。这是我到目前为止所得到的。该程序的参数是它包含 2 个函数，主函数和第二个函数，它将对传递的值进行二进制排序。该程序有效，但它不递归搜索函数，我不认为它使用二进制搜索......

/* ex06_18.c */
#include <stdio.h>
#define SIZE 10

/* function prototype */
void someFunction( const int b[], int startIndex, int size );

/* function main begins program execution */
int main( void )
{
int a[ SIZE ] = { 8, 3, 1, 2, 6, 0, 9, 7, 4, 5 }; /* initialize a */
printf( "Answer is:\n" );
someFunction( a, 0, SIZE );
 printf( "\n" );
return 0; /* indicates successful termination */
}
void someFunction( const int b[], int startIndex, int size )
{
if ( startIndex < size ) {
someFunction( b, startIndex + 1, size );
printf( "%d ", b[ startIndex ] );
} /* end if */
} /* end function someFunction */
4

2 回答 2

0

您正在做的只是向后打印数组，不是吗？您可以在http://en.wikipedia.org/wiki/Binary_search_algorithm中阅读二进制搜索算法。我看不出你有什么理由说它“必须”是一个递归函数。我更喜欢二进制搜索的非递归函数，即使在维基百科链接中它也有递归方法。

于 2013-10-24T03:32:07.753 回答
0

二进制搜索仅在您的数据集已排序时才有效；否则小于和大于比较是完全没用的，因为它们不会告诉你任何其他元素在哪里。所以首先你需要确保你的数据集是排序的——这是一个单独的问题。

一旦你有了一个排序的数据集，你就试图想出一个遵循这种通用形式的函数（伪代码，而不是实际的 C++）：

function search(needle, haystack, start, end) {
    int middle_idx = haystack[(start+end)/2]
    if(haystack[middle_idx] == needle)
        return middle_idx;
    else if(haystack[middle_idx] < needle)
        return search(needle, haystack, start, middle_idx-1)
    else if(haystack[middle_idx] > needle)
        return search(needle, haystack, middle_idx+1, end)

确保处理弹出的任何边缘情况。特别是，想想如果在大海捞针中找不到针会发生什么；你能添加一些处理这种情况的东西吗？

于 2013-10-24T03:39:13.003 回答