C++ - Trouble Understanding a Divide and Conquer Function

Question

I'm having trouble understanding how this divide and conquer function compares data elements:

int main()
{
  int arr[] = { -5, -10, -16, -3, -7 };
  int largest;

  largest = largest_element(arr, 0, sizeof(arr) / sizeof(int));
  cout << "Largest element in arr is " << largest << ".\n";

  return 0;
}

int largest_element(const int *a, int begin, int past_end)
{
  int result;
  int mid;
  int left_large;
  int right_large;

  assert(begin >= 0);
  assert(begin < past_end);

  if (past_end - begin == 1)
    result = a[begin];
  else {
    mid = (begin + past_end) / 2;
    left_large = largest_element(a, begin, mid);
    right_large = largest_element(a, mid, past_end);
    if (left_large >= right_large)
      result = left_large;
    else
      result = right_large;
  }

  //STOP! draw tree here when begin == 1, and past_end == 2.
  return result;
}

I understand that the array is simply divided into smaller sub arrays, and that once the base case is reached, it'll return a[begin]. However, based on my diagram, I don't understand how the values are truly compared if when we have an array of two elements, it simply returns the first value. For example, how will the right most element in an array be compared if it has nothing else to compare with?

Here is my diagram. I have no other diagrams to compare mine with.

Answer 1

I don't understand how the values are truly compared if when we have an array of two elements, it simply returns the first value.

I am unable to reproduce that finding. When arr has only 2 elements, the function still returns the larger of the two.

Your debugger is an appropriate way to evaluate your code and identify what you are misunderstanding.

However, it might be fun to add diagnostics and allow the code to report it's progress. Here is one technique:

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cassert>


class T548_t
{
   int depth;

public:

   T548_t() = default;
   ~T548_t() = default;

   int exec()
      {
         {
            depth = 0;  // 0    1    2   3   4
            int arr[] = { -5, -10, -16, -3, -7 }; // -3 is largest
            uint sz = sizeof(arr) / sizeof(int);
            std::cout << hdr(sz);

            std::cout << "\n\n  Largest element in arr is  "
                      << largest_element(arr, 0, sz)
                      << ".\n" << std::endl;
         }
         {
            depth = 0;
            int arr[] = { -10, -5 }; // -5 is largest
            uint sz = sizeof(arr) / sizeof(int);
            std::cout << hdr(sz);

            std::cout << "\n\n  Largest element in arr is  "
                      << largest_element(arr, 0, sz)
                      << ".\n" << std::endl;
         }
         return 0;
      }

private: // methods

   int largest_element(const int* a, int begin, int past_end)
      {
         int result;
         int mid;
         int left_large;
         int right_large;

         assert(begin >= 0);
         assert(begin < past_end);

         std::cout << show(a, begin, past_end) << std::flush;

         if (past_end - begin == 1)
            result = a[begin];
         else {
            mid = (begin + past_end) / 2;
            left_large  = largest_element(a, begin, mid);
            right_large = largest_element(a, mid, past_end);

            if (left_large >= right_large)
               result = left_large;
            else
               result = right_large;
         }

         //STOP! draw tree here when begin == 1, and past_end == 2.
         depth -= 1;
         return result;
      }

   std::string show(const int* a, int b, int e)
      {
         std::stringstream ss;
         depth += 1;
         ss << "\n  a[" << b << " .. " << e-1 << "]    " 
            << depth << "   ";

         if(b > 0)
            ss << std::setw(4*b) << " ";

         for (int i = b; i < e; ++i)
            ss << std::setw(4) << a[i];

         return ss.str();
      }

   std::string hdr(uint sz)
      {
         std::stringstream ss;
         ss << "\n  "
            << "  b .. e"
            << std::setw(8) << "depth"
            << std::setw(4) << " ";
         for (uint i=0; i<sz; ++i)
            ss << i << "   ";
         return ss.str();
      }

}; // class T548_t

int main(int, char**)
{
   T548_t   t548;
   return t548.exec();
}

Here is the output:

    b .. e   depth    0   1   2   3   4   
  a[0 .. 4]    1     -5 -10 -16  -3  -7
  a[0 .. 1]    2     -5 -10
  a[0 .. 0]    3     -5
  a[1 .. 1]    3        -10
  a[2 .. 4]    2            -16  -3  -7
  a[2 .. 2]    3            -16
  a[3 .. 4]    3                 -3  -7
  a[3 .. 3]    4                 -3
  a[4 .. 4]    4                     -7

  Largest element in arr is  -3.


    b .. e   depth    0   1   
  a[0 .. 1]    1    -10  -5
  a[0 .. 0]    2    -10
  a[1 .. 1]    2         -5

  Largest element in arr is  -5.