For an array of size N, what is the # of comparisons required?
+1
A:
You can find the second largest value with at most 2·(N-1) comparisons and two variables that hold the largest and second largest value:
largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
number := numbers[i];
if number > largest then
secondLargest := largest;
largest := number;
else
if number > secondLargest then
secondLargest := number;
end;
end;
end;
Gumbo
2010-09-02 15:43:51
That's more than N-1.
sdcvvc
2010-09-02 15:47:56
N-1 is wrong, check i.e. {1,4,2,3,5}
x4u
2010-09-02 15:50:08
How do you find 2 largest elements in a set of 3 using 2 comparisons?
Maciej Hehl
2010-09-02 15:50:18
@sdcvvc: Yes, but I guess he’s aiming for the complexity. And that’s O(*N*).
Gumbo
2010-09-02 15:50:40
Your algorithm doesn't work for {1,3,2}. It would return 1 instead of 2.
x4u
2010-09-02 15:57:51
-1. Your algorithm does not work. Try it on the input "3,5,4".
Stargazer712
2010-09-02 15:59:51
@x4u, @Stargazer712: Fixed that.
Gumbo
2010-09-02 16:03:35
Much better. Removed the -1.
Stargazer712
2010-09-02 16:05:28
A:
Sort the array into ascending order then assign a variable to the (n-1)th term.
Garee
2010-09-02 15:46:13
A:
Assuming space is irrelevant, this is the smallest I could get it. It requires 2*n comparisons in worst case, and n comparisons in best case:
arr = [ 0, 12, 13, 4, 5, 32, 8 ]
max = [ -1, -1 ]
for i in range(len(arr)):
if( arr[i] > max[0] ):
max.insert(0,arr[i])
elif( arr[i] > max[1] ):
max.insert(1,arr[i])
print max[1]
Stargazer712
2010-09-02 15:46:51
+4
A:
Here is optimal algorithm taking n+log n-2 comparisons, with proof of optimality. Also, use Google.
sdcvvc
2010-09-02 15:47:14
+1 because it's better than the incorrect answers, but SO is designed to be a repository of information (and to appear in the results of Google searches), not just a bunch of links ;-)
Steve Jessop
2010-09-02 16:00:08
A:
Here is some code that might not be optimal but at least actually finds the 2nd largest element:
if( val[ 0 ] > val[ 1 ] )
{
largest = val[ 0 ]
secondLargest = val[ 1 ];
}
else
{
largest = val[ 1 ]
secondLargest = val[ 0 ];
}
for( i = 2; i < N; ++i )
{
if( val[ i ] > secondLargest )
{
if( val[ i ] > largest )
{
secondLargest = largest;
largest = val[ i ];
}
else
{
secondLargest = val[ i ];
}
}
}
It needs at least N-1 comparisons if the largest 2 elements are at the beginning of the array and at most 2N-3 in the worst case (one of the first 2 elements is the smallest in the array).
x4u
2010-09-02 16:09:26