为“分而治之”算法寻找数组指标？

Question

我必须在C++中为max函数实现分治算法，该函数返回数组中的最大值。我理解算法并已经设计了函数，但我遇到了数组索引的问题。

在伪代码中，下面是我的函数：

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;

有没有办法找到这些导致正确行为的指数？我很感激你的帮助。

Answer 1

应该是

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