Divide and conquer largest two elements

Divide and conquer largest two numbers problem

Given an array of integers. Find the first and second largest elements in the array. Use divide and conquer technique.

Divide and conquer algorithm largest two elements

Simply divide the array into two halves then find the largest two elements in each half. At the end you need to return the largest two out of the four because each half returns two elements. The base case for recursion is when the array contains one or two elements. In that case the largest two elements are the first and the second elements of the array.

Notice that this algorithm runs in linear time like the one and two loops solutions but the number of comparisons made is less.

Code

Here is a c++ code for divide and conquer first and second largest numbers using a single loop

//Includes
#include <iostream>

//STD
using namespace std;

//Result record
struct Result
{
   int max1;
   int max2;
};

//Receives input array along with left
//and right array indices which are used
//to split the array into two halves
Result FirstSecondMax(int A[], int l, int r)
{
	//Output result
	Result res;
	res.max1 = A[l];
	res.max2 = A[l];
	
	//if array has only one element return null record
	if (l == r) return res;
	
	//Base case when array has only two elements
	if (r - l == 1)
	{
		//If the right element is greater than
		//the left element then the right element
		//is the first maximum
		if (A[r] >= A[l])
		{
			res.max1 = A[r];
			res.max2 = A[l];
		}
		else
		{
			res.max1 = A[l];
			res.max2 = A[r];
		}
		
		return res;
	}

   //Find middle element
   int m = (l + r)/2;
   
   //Find the largest two elements in each half
   Result lres = FirstSecondMax(A, l, m);
   Result rres = FirstSecondMax(A, m + 1, r);

   //So far we got 4 max values 2 on each half
   //so we need to merge them and take out only
   //two. Basically you compare the largest element
   //on the right side with the largest element on
   //the left side and take the greater one as the
   //result first max. In case the taken one was the
   //first max on the right then you need to compare
   //the second max on the right with the first max
   //on the left. If it is greater then you take it
   //as the second max otherwise you take the first
   //max on the left as the result second max. You
   //do the same if the taken one was on the left.
   //The code segment below demonstrates that

   //First max on the right is greater than
   //first max on the left
   if (rres.max1 >= lres.max1)
   {
	   //Take the first max on the right
	   res.max1 = rres.max1;

	   //Compare second max on the right with
	   //first max on the left
	   if (rres.max2 >= lres.max1)
	   {
		   res.max2 = rres.max2;
	   }
	   else
	   {
		   res.max2 = lres.max1;
	   }
   }
   //First max on the left is greater than
   //first max on the right
   else
   {
	   //Take the first max on the left
	   res.max1 = lres.max1;

	   //Compare second max on the left with
	   //first max on the right
 	   if (lres.max2 >= rres.max1)
	   {
		   res.max2 = lres.max2;
	   }
	   else
	   {
		   res.max2 = rres.max1;
	   }
  }

   return res;
}

//Main function
void main()
{
	//Input array
	int A[] = {1, 5, 2, 4, 3};

	//Find first and second max elements
	Result res = FirstSecondMax(A, 0, 4);

	//Print output
	cout << res.max1 << " : " << res.max2 << endl;
}

Thanks for reading. Please use the comments section below for feedback.

Leave a Reply

%d bloggers like this: