Working Mechanism for Finding the Maximum and Minimum using Divide and Conquer Technique

For Complete YouTube Video: Click Here

In this class, we will try to understand Working Mechanism for Finding the Maximum and Minimum using Divide and Conquer technique.

To understand the concept better, we will consider the array of elements shown below.

As the algorithm design uses the divide and conquers technique, we will divide the problem into sub-problems.

The division of the problem into sub-problems is done based on the mid-value of the array.

We will find the mid-value by using the following formula.

mid = FLOOR(( Low+ High ) / 2).

If we apply the mid-value on the above array, the index will be at four.

The division of the array after applying the mid will be as shown below.

The division is applied so that the element in the sub-problem should be two or less than two.

The image below is the recursive tree obtained on the above array.

Now, we will find the maximum and minimum values on the sub-problems.

In our case, we will find the max1 and min1 on the array with index 0, 1.

The max1 is 7, and the min1 is 4.

Similarly, we will find the max2 and min2 on the right-hand part of the sub-problem.

The max2 and min2 in the right-hand part of the sub-problem with index two are three.

Now, we will find the max and min by comparing the max1, max2, and min1, min2.

In our case, the max and min are seven and three.

Similarly, we will solve all the sub-problems.

Finally, the max and min values are nine and one.