我不明白为什么我的递归函数没有按预期运行

Question

我正在尝试创建一个函数，该函数 return 是数组中给定整数最右边位置的位置。示例：[1,2,3,4,5,6] 找到 4 的最右边位置将 return 4. [1,2,3,4,4,4,5,6] 找到最右边位置4 将 return 6.

我正在尝试在我的函数中实现递归调用。打印出递归调用时，我看到了正确的位置，尽管我最终遇到了麻烦 returning 该数字。

#include <stdio.h>

int RightMostBinarySearch(int *arr, int length, int find, int i, int j) {
    int middle = (i + j) / 2; //This will be floor due to integer data type
    while(i <= j){ //While the start does not excede int size of last value in array
        if(arr[middle] < find){ //If middle element is less than what is being searched for
            i = middle + 1; //Obviously the element is not found and the element is greater than middle point => make i one element to the right
        }
        else if(arr[middle] == find){ //The middle position is where the element exists in the array
            printf("%d\n", RightMostBinarySearch(arr, length, find, middle + 1, j));
            return middle + 1;
        }
        else{ //This condition will be when arr[midd] > find
            j = middle - 1; // make j 1 element left of middle because find is less than arr[middle]
        }
        middle = (i + j) / 2; //if not found i or j changes, thus middle must also change.
    }
    return -1;
}

int main(void) {
    int arr[] = { 1, 2, 4, 4, 4, 4, 4, 9, 12 }; //Sorted int array of size n
    int find = 4;
    int length = sizeof(arr) / sizeof(*arr); // Determines the length by getting the full size of memory array uses and dividing by he size of first element memory size. Full memory / element memory = num elements = length
    int i = 0;
    int j = length - 1; // Length of array is n, last element is represented n - 1
    int location = RightMostBinarySearch(arr,length, find, i, j);
    printf("The location of the element is at position: %d\n", location);
    return 0;
}

Answer 1

当函数 RightMostBinarySearch 递归时，您打印它的 return 值但总是 return middle + 1，这甚至可能不是 [=14= 的偏移量] 值出现。

你应该这样修改函数：

int RightMostBinarySearch(int *arr, int length, int find, int i, int j) {
    //While the start does not exceed int size of last value in array
    while (i <= j) {
        // This will be floor due to integer data type
        // Also avoid potential integer overflow in i+j
        // make sure the middle element is > i unless i == j
        int middle = i + (j - i + 1) / 2;
        //If middle element is less than what is being searched for
        if (arr[middle] < find) {
            //Obviously the element is not found and the element is greater than middle point => make i one element to the right
            i = middle + 1;
        } else
        if (arr[middle] == find) {
            //The middle position is where the element exists in the array
            if (middle == j) {
                /* middle is the last possible value */
                return middle;
            } else {
                return RightMostBinarySearch(arr, length, find, middle, j));
            }
        } else {
            //This condition will be when arr[midd] > find
            j = middle - 1; // make j 1 element left of middle because find is less than arr[middle]
        }
    }
    return -1;
}

请注意，这个问题不用递归函数也可以很容易地解决，用一个更简单的 API:

#include <stdio.h>

int LeftMostBinarySearch(const int *arr, int length, int find) {
    int i = 0;
    int j = length;

    while (i < j) {
        // compute mid-point avoiding potential overflow on i+j
        int middle = i + (j - i) / 2;
        if (arr[middle] < find) {
            i = middle + 1;
        } else {
            j = middle;
        }
    }
    if (i < length && arr[i] == find)
        return i;
    else
        return -1;
}

int RightMostBinarySearch(const int *arr, int length, int find) {
    int i = 0;
    int j = length;

    while (i < j) {
        // compute mid-point avoiding potential overflow on i+j
        int middle = i + (j - i) / 2;
        if (arr[middle] <= find) {
            i = middle + 1;
        } else {
            j = middle;
        }
    }
    if (i > 0 && arr[i - 1] == find)
        return i - 1;
    else
        return -1;
}

int main() {
    int arr[] = { 1, 2, 4, 4, 4, 4, 4, 9, 12 }; //Sorted int array
    int length = sizeof(arr) / sizeof(*arr); // Determines the length by getting the full size of memory array and dividing by the size of first element. Full memory / element memory = num elements = length
    int find = 4;
    int left_location = LeftMostBinarySearch(arr, length, find);
    int right_location = RightMostBinarySearch(arr, length, find);
    printf("The first element %d is at position: %d\n", find, left_location);
    printf("The last element %d is at position: %d\n", find, right_location);
    return 0;
}

Answer 2

如果您使用递归，我认为您不需要 while 循环？

我认为您可以通过以下方式找到此问题的解决方案。正如我所见，您应该 return 每一步。

int rmst(int *arr, int length, int find, int i, int j){                         
    if (i <= j) {                                                               
        int middle = (i+j)/2;                                                   
        if (arr[middle] < find){                                                
            return rmst(arr, length, find, middle+1, j);                        
        } else if (arr[middle] == find){                                        
            if ((middle + 1) < length){                                         
                if (arr[middle + 1] == find){ // continue binary search if the next guy is still == find, otherwise, return middle.                                   
                    return rmst(arr, length,find, middle+1, j);                
                }                                                               
            }                                                                   
            return middle;                                                      
        } else {                                                                
            return rmst(arr, length, find, i, middle -1);                       
        }                                                                       
    }                                                                           
                                                                                
    return -1;                                                                  
}

Answer 3

首先C中数组的索引从0开始。

其次，您的函数中未使用参数 length 的值。

第三，如果第一个 if 条件的计算结果为真，那么实际上您没有递归函数。您有一个带有 while 循环的迭代函数。

while(i <= j){ //While the start does not excede int size of last value in array
    if(arr[middle] < find){ //If middle element is less than what is being searched for
        i = middle + 1; //Obviously the element is not found and the element is greater than middle point => make i one element to the right
    }

    //...

    middle = (i + j) / 2; //if not found i or j changes, thus middle must also change.
}

因此，当变量 find 的值大于数组中的任何元素时，您就有了一个完全迭代的函数。

当这个if语句

    else if(arr[middle] == find){ //The middle position is where the element exists in the array
        printf("%d\n", RightMostBinarySearch(arr, length, find, middle + 1, j));
        return middle + 1;
    }

计算结果为真然后调用

RightMostBinarySearch(arr, length, find, middle + 1, j)

没有效果，函数 returns middle + 1 的值与 arr[middle + 1] 是否确实等于 find 无关。

函数参数过多。

最后，指定数组的参数应具有限定符 const，因为数组本身不会在函数内更改。

函数的声明和定义如下面的演示程序所示。

#include <stdio.h>

size_t RightMostBinarySearch( const int *a, size_t n, int value )
{
    if (n == 0)
    {
        return -1;
    }
    else if ( value < a[n / 2] )
    {
        return RightMostBinarySearch( a, n / 2, value );
    }
    else if ( a[n / 2] < value )
    {
        size_t result = RightMostBinarySearch( a + 1 + n / 2, n - 1 - n / 2, value );
        return result == -1 ? result : result + 1  + n / 2;
    }
    else
    {
        size_t result = RightMostBinarySearch( a + 1 + n / 2, n - 1 - n / 2, value );
        return result == -1 ? n / 2 : result + 1 + n / 2;
    }
}

int main( void )
{
    int a1[] = { 1, 2, 3, 4, 5, 6 };
    const size_t N1 = sizeof( a1 ) / sizeof( *a1 );

    printf( "%zu\n", RightMostBinarySearch( a1, N1, 4 ) );

    int a2[] = { 1, 2, 3, 4, 4, 4, 5, 6 };
    const size_t N2 = sizeof( a2 ) / sizeof( *a2 );

    printf( "%zu\n", RightMostBinarySearch( a2, N2, 4 ) );
}

程序输出为

3
5

如您所见，递归函数中既没有 while 语句也没有任何其他循环。

我不明白为什么我的递归函数没有按预期运行

I am not understanding why my recursive function is not behaving as I expect

c

algorithm

sorting

recursion