Divide and Conquer
In Divide and Conquer method, we'll implement the following steps.
- Divide the array into two parts.
- Find the minimum and maximum of both the parts recursively.
- Take the minimum and maximum values of both the parts, compare them, and then find the minimum and maximum value of the entire array.
Next, we'll have a look at the Pseudocode:
Pseudocode
SNIPPET
1int[] findMinimumAndMaximum(int begin, int end,int input[])
2{
3 int maximum;
4 int minimum;
5 if ( begin == end )
6 {
7 minimum = input[begin]
8 maximum = input[begin]
9 }
10 else if ( begin + 1 == end )
11 {
12 if ( input[begin] < input[end] )
13 {
14 minimum = input[begin]
15 maximum = input[end]
16 }
17 else
18 {
19 minimum = input[end]
20 maximum = input[begin]
21 }
22 }
23 else
24 {
25 int midpoint = begin + (end - begin)/2
26 int leftArray[] = findMinimumAndMaximum(begin, midpoint, input)
27 int rightArray[] = findMinimumAndMaximum(midpoint+1, end, input)
28 if ( leftArray[0] > rightArray[0] )
29 maximum = leftArray[0]
30 else
31 maximum = rightArray[0]
32 if ( leftArray[1] < rightArray[1] )
33 minimum = leftArray[1]
34 else
35 minimum = rightArray[1]
36 }
37
38 int result[2] = {maximum, minimum}
39 return result
40}Now let's head straight to the implementation in Python, JavaScript, and Java:
xxxxxxxxxx46
document.write("Maximum value in an array is ", result.maximum);function findMinimumAndMaximum(input , begin , end) { result = new Array(); var result_left = new Array(); var result_right = new Array(); var midpoint; if (begin == end) { result.maximum = input[begin]; result.minimum = input[begin]; return result; } if (begin + 1 == end) { if (input[begin] > input[end]) { result.maximum = input[begin]; result.minimum = input[end]; } else { result.maximum = input[end]; result.minimum = input[begin]; } return result; } midpoint = parseInt(begin+(end-begin)/2); result_left = findMinimumAndMaximum(input, begin , midpoint); result_right = findMinimumAndMaximum(input, midpoint + 1, end); if (result_left.minimum < result_right.minimum) { result.minimum = result_left.minimum;OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
