函数来查找数组中与给定值(在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;
}

我们学习了Divide and Conquer方法，这就是我递归实现它的原因。我试图计算我的解的渐近复杂度，以说明我的函数的效率。有人能帮忙吗？我不认为我的解决方案是最有效的。

Answer 1

代码对数组值执行n-1次比较(这很容易通过多种方式证明，例如通过归纳法，或者通过注意每次比较都会拒绝一个最佳元素，然后进行比较，直到只剩下一个索引为止(。递归的深度是ceil(lg(n((。

一个归纳证明看起来像这样：设C(n(是执行if(t2.val < t3.val)的次数，其中n=r-l+1。则C(1(＝0，并且对于n>1，对于一些a+b=n，a，b>根据归纳假设，C(n(=a-1+b-1+1=a+b-1=n-1。QED。注意，无论你如何选择m和l <= m < r，这个证明都是一样的。

除非你使用并行，否则这不是一个分而治之的问题，即使这样，线性扫描也可以有效地使用CPU的缓存，因此并行的实际好处将比你预期的要少(可能要少得多(。