finding Min and max element from given array using divide & conquer

Algorithm for finding Min and max element from given array using divide & conquer

1. Finding Min,Max element from array
Using Divide & Conquer
By: S. A. Jaipurkar
Asst. Prof.
MIT, Aurangabad. Maharashtra.

2. Finding Min,Max element from array
Using Divide & Conquer
Consider a simple problem that can be solved by divide
and conquer technique.
The Max-Min Problem in algorithm analysis:
finding the maximum and minimum value in an array.
Solution : 2 methods :
1. naive method
2. divide and conquer approach

3. Naïve Method
It is a basic method to solve any problem.
In this method, the maximum and minimum
number can be found separately.
To find the maximum and minimum numbers, the
following straightforward algorithm can be used.
Analysis : The number of comparison in Naive
method is 2n - 2.

The number of comparisons can be reduced
using the divide and conquer approach.

4. Find Max & Min element
Algorithm: Max-Min-Element (numbers[])
max := number[1]
min := number[1]
for i = 2 to n do
if number[i] > max then
max := number[i]
if number[i] < min then
min := number[i]
return (max, min)

5. Divide and Conquer Approach

In this approach, the array is divided into two
halves.

Then using recursive approach maximum and
minimum numbers in each halves are found.

Later, return the maximum of two maxima of
each half and the minimum of two minima of
each half.

6. Function MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low]
return((max, min))
else
max = A[low]; min = A[high]
return((max, min))
end if
else
mid = low+high/2
(max_l , min_l ) = MAXMIN(A, low, mid)
(max_r , min_r ) =MAXMIN(A, mid + 1, high)
end if
Set max to the larger of max_l and max_r ;
set min to the smaller of min_l and min_r
return((max, min)).

7. Function MAXMIN (A, low, high)
if (high − low + 1 = 2) then
if (A[low] < A[high]) then
max = A[high]; min = A[low]
return((max, min))
else
max = A[low]; min = A[high]
return((max, min))
end if
else
mid = low+high/2
(max_l , min_l ) = MAXMIN(A, low, mid)
(max_r , min_r ) =MAXMIN(A, mid + 1, high)
end if
Set max to the larger of max_l and max_r ;
set min to the smaller of min_l and min_r
return((max, min)).