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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
//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.
About Author
Mohammed Abualrob
Software Engineer @ Cisco
Hello sir, your code doesn’t work for some of the inputs, it gives same output as first max and second max in some
of the inputs. The proposed correction to be made is: you AND the conditions (rres.max1 != rres.max2) and
(lres.max1 != lres.max2) respectively with the already existing IF conditions at lines 77 and 95 respectively. In other words, you replace your lines 77 and line 95 with these lines respectively:
Line 77: if((rres.max2 >= lres.max1) && (rres.max1 != rres.max2))
Line 95: if((lres.max2 >= rres.max1) && ( lres.max1 != lres.max2 ))
Kindly update it!
Thanks.