CODEWITHSUNDEEP
arraysalgorithmrecursiondivide-and-conquer
Bobazonski
Bobazonski

Reputation: 1565

Finding array indicies for "divide-and-conquer" algorithm?

I have to implement a divide-and-conquer algorithm in C++ for a max function, which returns the maximum value in an array. I understand the algorithm and have designed the function already, but I am running into issues with the array indices.

In pseudocode, here is my function:

def max(array, startIndex, endIndex)

    // if there is only one element, return it
    if startIdx = endIdx
        return array[startIdx];

    leftHigh = max(array, startIdx, endIdx/2);
    rightHigh = max(array, endIdx/2 + 1, endIdx);

    return maximum of leftHigh and rightHigh;

However, I run into an issue with these values for the recursive call parameters. The following paragraph demonstrates what I found when I mentally stepped through the algorithm:

The simplest case is an array of 4 elements. The first call to max will take index parameters 0, 3, and will make the calls with parameters 0, 1 and 2, 3. The first recursive call will result in calls with 0, 0 and 1, 1 which will terminate correctly. However, the second recursive call will result in calls with 2, 1 and 2, 3. The first eventually results in overstepping the array bounds and the second results in an infinite loop since those parameters have already been used.

I have tried messing with it, for example using (startIdx, endIdx/2 -1) for the first bounds and (endIdx/2, endIdx) for the second bounds, and this fixes the second branch of recursive calls but messes up the first.

Is there a way to find these indices resulting in the correct behavior? I appreciate the help.

Upvotes: 1

Views: 1710

Answers (3)

Yourpalal
Yourpalal

Reputation: 496

If I give you two numbers: a < c, then how would you characterise any numbers in between the two. I.E, what can we say about b when a < b < c ?

a < b < c
0 < b - a < c - a

You are picking b = c/2. Which we can see only meets the above criteria in some cases:

                b = c / 2
and             b > a
then            c / 2 > a

So we can see that your method works as long as a > c/2. In your case a = startIdx and c = endIdx, so your algorithm works only while startIdx < endIdx / 2.

Consider this finding carefully:

a < b < c
0 < b - a < c - a (subtract a from all parts)

If b is half-way between a and c, then what is its value? In this case, how does (b - a) relate to (c - a)?

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53535

Suggested solution in Python:

from math import floor, ceil
def maximum(arr, left, right):
    if left >= right:
        if left < len(arr):
            return arr[left]
        else:
            return arr[right]
    else:
        left = maximum(arr, left, int((left+right)/2)) # pay attention to the midpoint!
        right = maximum(arr, int((left+right)/2), right)
        return max(left, right)

print maximum([1,8,2,9,3,15,5,3,2], 0, 8)

OUTPUT

15

Upvotes: 0

Qmick Zh
Qmick Zh

Reputation: 565

It should be 

leftHigh = max(array, startIdx, (startIdx + endIdx)/2);
rightHigh = max(array, (startIdx + endIdx)/2 + 1, endIdx);

Upvotes: 1

Related Questions