# Algorithm to find the second smallest element

I am having trouble with the following homework assignment:

Give an algorithm that finds the second smallest of n elements in at most $n + \lceil\log(n)\rceil - 2$ comparisons.

I have been trying to find an algorithm myself, and believe I have to check the elements in pairs and then recurse on the smallest elements. However, when I tried an algorithm like this the amount of comparisons it took where $n + \lceil\log(n)\rceil$ (according to me).

This is the algorithm in question:

1. secondSmallest(A[n])
2.    if A.length >= 2 then
3.       for i = 1 to i = A.length do
4.          if A[i] < A[i + 1] then
5.             B[(i+1)/2] = A[i]
6.             i + +
7.          else
8.             B[(i+1)/2] = A[i + 1]
9.            i + +
10.         endif
11.      return secondSmallest(B[n])
12.    else
13.       if A[1] < A[2] then
14.          return A[2]
16.       else return A[1]
17.       endif
18.    endif


Note: this is pseudocode, and by no means accurate. And the logarithm is a BASE 2 logarithm.

-
Is that supposed to be a natural logarithm? Or base 2 perhaps? –  Harald Hanche-Olsen Mar 4 '12 at 14:53
What about binary searching for the smallest element using lg(n) comparisons, removing the smallest element from the array, and then do another binary search on the array using lg(n) comparisons and returning the smallest element. That would be lg(n) + lg(n) comparisons. –  SuprDewd Mar 4 '12 at 14:59
Oh, I am indeed very sorry. It is supposed to be a base 2. –  Ruddie Mar 4 '12 at 15:00
@SuprDewd Yes, I found that myself to. But we are meant to find one that takes n+lg(n)-2. Mainly because that would in fact be faster then your solution (since we would have to move all elements when doing that) –  Ruddie Mar 4 '12 at 15:04
@SuprDewd That requires the array to be sorted. It can be done in $n + \lg(n) - 2$ comparisons for any input array. –  Zach Langley Mar 4 '12 at 15:09

SKETCH: Assuming that you’re allowed to use extra storage, run the comparison as a single elimination tournament, keeping a record of the entries beaten by each winner along the way. (Low number wins.) When you get an overall winner, you have only to identify the winner among the $\lceil \lg n\rceil$ contestants beaten by the overall winner.

Added: On further thought, I see that one doesn’t actually need additional memory, if one rearranges the list. Implement the single elimination tournament as follows.

Suppose that the numbers are $a_0,a_1,\dots,a_{n-1}$. On the first pass compare $a_{2k}$ with $a_{2k+1}$ for $0\le k<(n-1)/2$; if $a_{2k}>a_{2k+1}$, interchange them. On the second pass compare $a_{4k}$ with $a_{4k+2}$ for $0\le k<(n-2)/4$; if $a_{4k}>a_{4k+2}$, interchange the pair $\langle a_{4k},a_{4k+1}\rangle$ with the pair $\langle a_{4k+2},a_{4k+3}\rangle$. On the $i$-th pass compare $a_{2^ik}$ with $a_{2^ik+2^{i-1}}$ for $0\le i<(n-2^{i-1})/2^i$; if $a_{2^ik}>a_{2^ik+2^{i-1}}$, interchange the blocks of length $2^{i-1}$ beginning at $a_{2^ik}$ and $a_{2^ik+2^{i-1}}$. This continues as long as $n-2^{i-1}>0$, i.e., until $n\le 2^{i-1}$; thus, if the last pass is the $m$-th pass, then $2^{m-1}<n\le 2^m$, or $\lceil\lg n\rceil=m$. The smallest number in the set is now $a_0$, and every other number in the set has lost exactly one comparison, so we’ve made $n-1$ comparisons.

The numbers that are now $a_{2^i}$ for $i=0,\dots,m-1$ are the numbers that lost to $a_0$ in direct comparisons; every number in the set that is neither $a_0$ nor one of these $m$ numbers lost a direct comparison to one of these $m$ numbers and therefore cannot be the second-smallest number in the set. Thus, the second-smallest number is the smallest of the $a_{2^i}$ for $i=0,\dots,m-1$. There are $m$ of these numbers, so it takes $m-1$ comparisons to find the smallest.

Altogether, then, this algorithm takes $$(n-1)+(m-1)=n-1+\lceil\lg n\rceil-1=n+\lceil\lg n\rceil-2$$ comparisons, as required.

-
You mean $\lceil \log n\rceil$, correct? –  Mike Mar 4 '12 at 15:53
@Mike: I sure do; thanks. Fixed. –  Brian M. Scott Mar 4 '12 at 16:06
So, you first get the smallest element in the array, taking n comparisons. And then you use a divide and conquer algorithm to find the smallest one out of the remaining elements (which would then take log(n) comparisons, however since you lack one element it would take log(n)-2 comparisons)? –  Ruddie Mar 4 '12 at 17:07
@Ruddie: No, that’s not at all what I described. The first pass takes $n-1$ comparisons, arranged in a binary tree; the second pass involves only $\lceil\lg n\rceil$ numbers and does $\lceil\lg n\rceil-1$ comparisons. –  Brian M. Scott Mar 4 '12 at 17:19
In the list of entries beaten by each winner the second smallest element is either first or second so finding it needs only one comparison. –  David Marquis Mar 4 '12 at 17:45

Consider the following list of numbers: $3, 4, 5, 2, 1, 7, 8, 9$.

While passing through the first stage of Brian M. Scott's algorithm above, after each pass the list changes as follows: $$\begin{array}{l|cccccccc} & a_0 & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 \\ \hline \text{start} & 3 & 4 & 5 & 2 & 1 & 7 & 8 & 9 \\ \text{pass 1} & 3 & 4 & 2 & 5 & 1 & \color{blue}{7} & 8 & 9 \\ \text{pass 2} & 2 & 4 & 3 & 5 & 1 & \color{blue}{7} & \color{blue}{8} & 9 \\ \text{pass 3} & 1 & 4 & 3 & 5 & \color{blue}{2} & \color{blue}{7} & \color{blue}{8} & 9 \end{array}$$

(The numbers in blue are those that have been compared to the final $a_0$ (that is, $1$) up to (and including) that pass through the algorithm.)

Brian M. Scott then states

The numbers that are now $a_{2^i}$ for $i=0,\ldots,m−1$ are the numbers that lost to $a_0$ in direct comparisons;...

However neither $4$ nor $3$ were ever compared directly to $1$, and the indicies of $7$ and $8$ are not of that form.

Have I missed something?

-
No, you’ve not missed something; I didn’t state the algorithm quite right. At each stage you have to interchange blocks rather than just the two numbers being compared. I’ve revised the answer accordingly. –  Brian M. Scott Jun 28 '12 at 19:46