WEEK#14 Divide and Conquer_Param

When we try to divide an array into 2 halves, we need to specify 3 parameters:

1. Which index does the left array start with? begin
2. Which index does the right array start with? mid
3. Which index does the right array end? end

So naturally, the array can be divided into two halves of
[0...mid-1] and [mid...end]
Note that initially, the begin of left array is 0, and the end of the right array is (the size of the array - 1)

Mid

Mid = (end + begin) / 2;

Begin

In left array, 'begin' remains,
begin = begin;
While in right array,
begin = mid;

End

In left array,
end = mid - 1;
in Right array,
end = end;

In all, we can write a function as follow to divide any array:

void Array_Division(vector<int>& arr, int begin, int mid, int end) {
     //for left array
     Array_Division(arr, begin, (mid-1+begin)/2, mid-1);
     //for right array
     Array_Division(arr, mid, (end+mid)/2, end);
}