查找数组中最接近给定值的数字的函数（在 C 中）

Question

我的任务是在数组中找到最接近给定值 t 的值。我们考虑绝对值。

我在 C:

中想出了以下函数

struct tuple
{
    int index;
    int val;
};
typedef struct tuple tuple;

tuple find_closest(int A[], int l, int r, int t)
{
    if(l == r)
    {
        tuple t1;
        t1.val = abs(A[l] - t);
        t1.index = l;
        return t1;
    }


    int m = (l+r)/2;
    tuple t2, t3;

    t2 = find_closest(A, l, m, t);
    t3 = find_closest(A, m+1, r, t);

    if(t2.val < t3.val)
    {
        return t2;
    }
    else
    {
        return t3;
    }
}


int main()
{
    int A[] = {5,7,9,13,15,27,2,3};

    tuple sol;

    sol = find_closest(A, 0, 7, 20);
    printf("%d", sol.index);

    return 0;
}

我们了解了分而治之的方法，这就是我递归实现它的原因。我正在尝试计算我的解决方案的渐近复杂性，以对我的函数的效率做出声明。有人可以帮忙吗？我不认为我的解决方案是最有效的。

Answer 1

该代码恰好对数组值执行 n-1 次比较（这很容易通过多种方式证明，例如通过归纳法，或者通过注意每次比较恰好拒绝一个元素成为最佳元素并且您进行比较直到只剩下一个索引）。递归的深度是ceil(lg(n)).

归纳证明看起来像这样：令 C(n) 为执行 if(t2.val < t3.val) 的次数，其中 n=r-l+1。则 C(1) = 0，对于 n>1，C(n) = C(a) + C(b) + 1 对于某些 a+b=n，a，b > 0。然后根据归纳假设， C(n) = a-1 + b-1 + 1 = a+b - 1 = n - 1. QED。注意这个证明无论怎么选m只要l <= m < r.

都是一样的

除非您使用并行机制，否则这不是分而治之的问题，即使这样，线性扫描也具有有效使用 CPU 缓存的好处，因此实际好处并行度将比您预期的要少（可能少很多）。

查找数组中最接近给定值的数字的函数（在 C 中）

Function to find the closest number in an array to a given value (in C)

c

complexity-theory