如何在递归函数 C 上使用二进制搜索找到元素？

Question

我写这个简码是为了在复杂度为 O(log n) 的排序数组（从高到低）中查找元素 x 的位置。 n 和 arr 代表数组的边缘。但是，它似乎无法正常工作。有什么建议吗？

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

对于 int arr[] = { 9, 7, 7, 5, 3, 3, 3, 1 };、int n = 8 和 int key = 3，当我应该得到 5.

时，我得到了 4

Answer 1

你的递归函数 returns 错误结果的原因是你应该将递归调用的结果偏移到递归调用中作为起点给出的数组开头的偏移量。仅当递归调用找到匹配项时才应执行此操作。

这是修改后的版本：

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

Answer 2

优化chqrlie的代码后，我得到了这个，它运行良好：

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

如何在递归函数 C 上使用二进制搜索找到元素？

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

c

recursion

binary-search