As the title says, is there any efficient way to find the second largest element in an array using recursion?
9
-
show us your code and we tell you if it is efficientnano_nano– nano_nano2013-01-10 15:44:49 +00:00Commented Jan 10, 2013 at 15:44
-
1Do you have to use recursion? It's rather easy to do without.Henry– Henry2013-01-10 15:45:52 +00:00Commented Jan 10, 2013 at 15:45
-
Efficiency and recursion are two different directions.sr01853– sr018532013-01-10 15:45:59 +00:00Commented Jan 10, 2013 at 15:45
-
Assuming it's unsorted, the simplest way would be to run through the array once, find the largest element, then run through again to find the largest element less than the largest. You could use recursion; it would recurse twice.Reinstate Monica -- notmaynard– Reinstate Monica -- notmaynard2013-01-10 15:47:23 +00:00Commented Jan 10, 2013 at 15:47
-
1@iamnotmaynard why pass twice if you can pass once?Luchian Grigore– Luchian Grigore2013-01-10 15:48:26 +00:00Commented Jan 10, 2013 at 15:48
|
Show 4 more comments
7 Answers
partition based Selection algorithm is recursive by nature, and it lets you select the k'th element in the array, so using it - you can actually find the answer for any k, including k = n-1 (your case).
This is done in O(n) on average with fairly low constants.
Comments
If nothing is known about the array, you can't do better than O(n), whether it's recursive or iterative.
Just pass throught the array recursively, while passing the two largest elements and replacing them if you find larger values.
find_largest(array_begin, largest, secondLargest)
if (array_begin = NULL)
return secondLargest
if (array_begin.value > largest)
secondLargest = largest
largest = array_begin.value
return find_largest(array_begin+1, largest, secondLargest)
largest and secondLargest can initially be set to the minimum you expect to find in the array.
You're right, sorting (at least full sorting) is overkill.
2 Comments
Neel
How can I set the minimum if nothing about the array is known? Do you mean the first elem?
Luchian Grigore
@Neel no additional info I mean - i.e. if you know that the array is sorted, you can do it in
O(1).Something in O(n) like this:
int findSecondLargest(int[] arr, int index, int largest, int secondLargest) {
if(index == arr.length) {
return secondLargest;
}
int element = arr[index];
if(element > secondLargest) {
if(element > largest) {
return findSecondLargest(arr, index + 1, element, largest);
} else {
return findSecondLargest(arr, index + 1, largest, element);
}
}
return findSecondLargest(arr, index + 1, largest, secondLargest);
}
Comments
public void recurs(int[] data, int ind, int max1, int max2){
if(ind<data.length){
if(data[ind]>max1){
int temp = max1;
max1 = data[ind];
max2 = temp;
} else if(data[ind]>max2){
max2 = data[ind];
}
recurs(data, ind+1, max1, max2);
} else {
return max2;
}
return -1;
}
to call it : recurs(dataX, 0, Integer.MIN_VALUE, Integer.MIN_VALUE);
Comments
Instinctively, you can scan the array and do comparison on every value twice. Anyway, you need O(n) to solve the problem. It's fast enough.
Try to avoid recursive when it is not necessary because it is not free.
Comments
If you do it by recursion then at most you have to do 3(n)/2-2 comparisons but for a better solution, think this problem as a binary tree with n numbers of nodes. Then there will be n-1 comparison for finding largest and log(n)-1 comparison for second largest. But some argue that it needs n + log(n) comparison.
Comments
function findTwoLargestNumber(n,startIndex,largestNumber,secondLargestNumber){
if(startIndex==arrlengths-1){
return [largestNumber,secondLargestNumber];
}
if(largestNumber<n[startIndex+1]){
secondLargestNumber=largestNumber;
largestNumber=n[startIndex+1];
}
return findTwoLargestNumber(n,startIndex+1 ,largestNumber,secondLargestNumber)
}
1 Comment
Community
As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.