How can you find an element using binary search on a recursive function C?

user_15184912 0
Viewed 196

I wrote this shortcode to find element x location in a sorted array (from high to low) with complexity O(log n). n and arr represent the edges of the array. However, it doesn't seem to work properly. Any suggestions?

int ex2_1(int *arr, int n, int key)
{
    if (n == 0)
        return -1;
    if (arr[n / 2] == key)
        return n / 2;
    if (arr[n / 2] > key)
        return ex2_1(arr + n / 2 + 1, n - n / 2 - 1, key);
    return ex2_1(arr, n / 2, key);
}

for int arr[] = { 9, 7, 7, 5, 3, 3, 3, 1 };, int n = 8 and int key = 3, I get 4 when I should get 5.

binary-search recursion c
2 Answers

The reason your recursive function returns erroneous results is you should offset the result of the recursive call by the offset from the start of the array given as starting point in the recursive call. This should only be done if the recursive call finds a match.

Here is a modified version:

int ex2_1(const int *arr, int n, int key) {
    int m = n / 2;

    if (n == 0)
        return -1;
    if (arr[m] == key)
        return m;
    if (arr[m] > key) {
        int res = ex2_1(arr + m + 1, n - m - 1, key);
        return res < 0 ? res : res + m + 1;
    } else {
        return ex2_1(arr, m, key);
    }
}
user_45932670

After optimization of chqrlie's code I got to this, and it works well:

int ex2_1(int* arr, int n, int key)
{
    if (n == 0) return -1;
    if (arr[n/2] == key) return n / 2;
    if (arr[n/2] > key)
    {
        int a = ex2_1(arr + n/2 + 1, n - n/2 - 1, key);
        if (a == -1) return -1;
        return n / 2 + 1 + a;
    }
    return ex2_1(arr, n/2, key);
}
user_151849120
Related