编译器正在跳过 return 行。递归二分查找

Question

我已经使用递归调用（忽略 printf 语句）制作了二进制搜索程序。在运行程序上，您会发现它运行良好并获取要查找的元素的索引，但在 :

else if (element == arr[mid])
    {
        printf("\n%d\nmid = %d\nstart = %d\nend = %d\n\n", i, mid,start,end);
        return mid;
    }

它没有 return 中间，而是 return 末尾的 0。（我尝试过 0 以外的值）。

我也尝试过 return 中间而不是 returning 0。它总是 returns 4.

整个代码为：

#include <stdio.h>

int arr[100]={0,1,2,3,4,5,6,7,8,9}, start=0, end=9, i=0;

int BinaryRecursivSearch(int element, int start, int end)
{
    int mid = (start + end)/2;

    i++;

    printf("\n%d\nmid = %d\nstart = %d\nend = %d\n\n", i, mid,start,end);

    if (mid == start)
    {
        if(element!=end)
        {
            printf("\nElement not found");
            return -1;
        }
    }

    else if (element < arr[mid])
        BinaryRecursivSearch(element, start, mid);

    else if (element > arr[mid])
        BinaryRecursivSearch(element, mid, end);

    else if (element == arr[mid])
    {

//For the last iteration (or recursion) mid has the correct value in printf

printf("\n%d\nmid = %d\nstart = %d\nend = %d\n\n", i, mid,start,end);
        return mid;  //It skips this
    }

    return 0;  //It returns this value
}

int main()
{
    int element, index;

    printf("Enter the element to be searched for: ");
    scanf("%d", &element);

    index = BinaryRecursivSearch(element, start, end);

    printf("\n Element found at %d position", index + 1 );

    return 0;

}

Answer 1

函数returns 0因为这些语句

BinaryRecursivSearch(element, start, mid);
...
BinaryRecursivSearch(element, mid, end);

应该是

return BinaryRecursivSearch(element, start, mid);
...
return BinaryRecursivSearch(element, mid, end);

因为他们没有return任何东西，最后的语句被执行

return 0;

Answer 2

我看不出你的功能有任何意义。例如我完全不明白这个代码片段是什么意思

if (mid == start)
{
    if(element!=end)
    {
        printf("\nElement not found");
        return -1;
    }
}

请注意，数组可以包含任何值，而不仅仅是您程序中的 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }。因此，此代码片段对于二进制搜索方法没有任何意义。尝试使用不同值的数组，您的程序将无法按预期运行。

或者在这段代码中

else if (element < arr[mid]) BinaryRecursivSearch（元素，开始，中间）；

else if (element > arr[mid]) BinaryRecursivSearch（元素，中间，结束）；

您没有使用函数 BinaryRecursivSearch 返回的值。

我建议把递归函数写得简单一些

这是一个演示程序，展示了如何编写该函数

#include <stdio.h>

int binary_search( const int a[], int n, int value )
{
    int middle;

    if ( n == 0 ) return -1;

    middle = n / 2;

    if ( value < a[middle] )
    {
        return binary_search( a, middle, value );
    }
    else if ( a[middle] < value )
    {
        int index = binary_search( a + middle + 1, n - middle - 1, value );
        return index == -1 ? -1 : index + middle + 1;
    }

    return middle;
}

#define N   10

int main(void) 
{
    int a[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    for ( int i = 0; i < N; i++ ) printf( "%d ", a[i] );
    printf( "\n" );

    for ( int i = -1; i <= N; i++ )
    {
        printf( "%d has index %d\n", i, binary_search( a, N, i ) );
    }

    return 0;
}

程序输出为

0 1 2 3 4 5 6 7 8 9 
-1 has index -1
0 has index 0
1 has index 1
2 has index 2
3 has index 3
4 has index 4
5 has index 5
6 has index 6
7 has index 7
8 has index 8
9 has index 9
10 has index -1

编译器正在跳过 return 行。递归二分查找

Compiler is skipping the return line. Binary Search by Recursion

c

recursion

binary-search