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

Question

I'm given the task to find the closest value in an array to a given value t. We consider the absolute value.

I came up with the following function in 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;
}

We learnt about the Divide and Conquer method which is why I implemented it recursively. I'm trying to compute the asymptotic complexity of my solution to make a statement about the efficiency of my function. Can someone help? I don't think that my solution is the most efficient one.

Answer 1

The code performs exactly n-1 comparisons of array values (which is easy to prove in several ways, for example by induction, or by noting that each comparison rejects exactly one element from being the best and you do comparisons until there's exactly one index left). The depth of the recursion is ceil(lg(n)).

An inductive proof looks something like this: let C(n) be the number of times if(t2.val < t3.val) is executed where n=r-l+1. Then C(1) = 0, and for n>1, C(n) = C(a) + C(b) + 1 for some a+b=n, a, b > 0. Then by the induction hypothesis, C(n) = a-1 + b-1 + 1 = a+b - 1 = n - 1. QED. Note that this proof is the same no matter how you choose m as long as l <= m < r.

This isn't a problem that divide-and-conquer helps with unless you are using parallelism, and even then a linear scan has the benefit of using the CPU's cache efficiently so the practical benefit of parallelism will be less (possibly a lot less) than you expect.