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

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

>Solution :

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
        int middle = i + (j - i) / 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
            int k = RightMostBinarySearch(arr, length, find, middle + 1, j));
            if (k < 0) {
                return middle;
            } else {
                return k;
            }
        } 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;
}