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

Question

I am trying to create a function that returns the position of the right most position of a given integer in an array. Example: [1,2,3,4,5,6] find right most position of 4 would return 4. [1,2,3,4,4,4,5,6] find right most position of 4 would return 6.

I am trying to implement a recursive call in my function. When printing out the recursive call I see the correct position, though I am having trouble ultimately returning that number.

#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

Firstly indices in arrays in C start from 0.

Secondly the value of the parameter length is not used in your function.

Thirdly if the first if condition evaluates to true then in fact you have not a recursive function. You have an iterative function with a while loop.

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.
}

So when the value of the variable find is greater than any element of the array you have a fully iterative function.

When this if statement

    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;
    }

evaluates to true then this call

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

has no effect and the function returns the value of middle + 1 independent on whether indeed arr[middle + 1] is equal to find.

The function has too many parameters.

And at last the parameter that specifiers the array shall have the qualifier const because the array itself is not being changed within the function.

The function can be declared and defined the following way as it is shown in the demonstration program below.

#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 ) );
}

The program output is

3
5

As you can see neither while statement or any other loop is present in the recursive function.

Answer 2

When the function RightMostBinarySearch recurses, you print its return value but always return middle + 1, which might not even be an offset with the find value appears.

You should modify the function this way:

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;
}

Note that this problem can be solved easily without a recursive function, with a simpler 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 3

if you are using recursion, I don't think you'd need the while loop?

Here is how I think you can arrive at the solution for this problem. You should return for every step as I see put.

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;                                                                  
}