0

So in my textbook there is this block of code to find the maximum element in an array by using the divide and conquer recursive algorithm:

Item max(Item a[], int l, int r)
{
    if (l == r) return a[1];
    int m = (l+r)/2;
    Item u = max(a, l, m);
    Item v = max(a, m+1, r);
    if (u > v) return u; else return v;
}

For one of the questions following the code, it asks me to modify that program so that I find the maximum element in an array by dividing an array of size N into one part of size k = 2^((lgN)-1) and another of size N-k (so that the size of at least one of the parts is a power of 2.

So I'm trying to solve that, and I just realized I wouldn't be able to do an exponent in code. How am I supposed to implement dividing one array into size k = 2^((lgN)-1)?

4
  • why do you need divide and conquer for this problem ? it is going to take same linear time as the original legacy solution
    – mangusta
    Mar 15, 2014 at 16:58
  • "I wouldn't be able to do an exponent in code" - why not? Mar 15, 2014 at 17:11
  • I'm just following problem here though. I'm mostly just confused as to how to split it into the size k = 2^((lgN)-1). I know how to do simple exponents such as 2^5 but the lgN-1 part is messing me up Mar 15, 2014 at 18:27
  • The first return: return a[1]; is wrong! Should be return a[l]; (or equivalent return a[r];).
    – CiaPan
    Oct 14, 2014 at 7:26

2 Answers 2

0

Both logs and exponentials can be computed using functions in the standard library.

But a simple solution would be to start at 1 and keep doubling until you reach a number bigger than desired. Going back one step then give you your answer.

(Of course the whole idea is mad - this algorithm is much more complex and slower than the obvious linear scan. But I'll assume there is some method in the madness.)

2
  • Thanks for the response.I know it probably isn't the most efficient but I think it's just to help us understand more about recursion. I'm still not quite sure about the code to split it into the size of k = 2^((lgN)-1) though Mar 15, 2014 at 18:25
  • That's what my second paragraph is about. You're looking for the largest power of two less than N. Keep doubling till you get there. Mar 15, 2014 at 18:50
0

This finds maximum k being a power of 2 and less than the number of array items (so the array part is divided into two non-empty parts):

Item max(Item a[], int l, int r)
{
    if (l == r) return a[r];

    int s = r-l, k = 1;
    while (2*k <= s)
        k = 2*k;

    Item u = max(a, l, l+k-1);
    Item v = max(a, l+k, r);
    return u > v ? u : v;
}

However this is not necessarily the best possible choice. For example you might want to seek such k which is closest to the half of the array's length (for 10 items that would be k=4 instead of 8).
Or you may try to partition the array into two parts both with lengths being powers of 2 (if possible, for 10 items it would be 8+2)...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.