title: Finding array indicies for "divide-and-conquer" algorithm?
body: <p>I have to implement a divide-and-conquer algorithm in C++ for a <code>max</code> 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.</p>
  
  <p>In pseudocode, here is my function:</p>
  
  <pre><code>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;
  </code></pre>
  
  <p>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:</p>
  
  <p>The simplest case is an array of 4 elements. The first call to <code>max</code> will take index parameters <code>0, 3</code>, and will make the calls with parameters <code>0, 1</code> and <code>2, 3</code>. The first recursive call will result in calls with <code>0, 0</code> and <code>1, 1</code> which will terminate correctly. However, the second recursive call will result in calls with <code>2, 1</code> and <code>2, 3</code>. The first eventually results in overstepping the array bounds and the second results in an infinite loop since those parameters have already been used.</p>
  
  <p>I have tried messing with it, for example using <code>(startIdx, endIdx/2 -1)</code> for the first bounds and <code>(endIdx/2, endIdx)</code> for the second bounds, and this fixes the second branch of recursive calls but messes up the first.</p>
  
  <p>Is there a way to find these indices resulting in the correct behavior? I appreciate the help.</p>