Algorithm to find high/low numbers with at most 1.5n comparisons

Question

I've been thinking about this homework question for a bit now. Given an number array of size n, design an algorithm that will find the high and and low values with at most 1.5n comparisons.

My first try was

int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted

for (i=0, i < n, i++) {
  if (numList[i] > high)
    high = numList[i]

  else if (numList[i] < low)
    low = numList[i]

}

My problem is each iteration of the loop has one of three possibilities:

• low value is found - 1 comparison made
• high value is found - 2 comparisons made
• neither is found - 2 comparisons made

So for an entire array traversal, a maximum of 2n comparisons can be made, which is a far cry from the problem maximum requirement of 1.5n comparisons.

Answer 1

Start with a pairs of numbers and find local min and max (n/2 comparisons). Next, find global max from n/2 local maxes (n/2 comparisons), and similarly global min from local mins (n/2 comparisons). Total comparisons: 3*n/2 !

For i in 0 to n/2: #n/2 comparisons
    if x[2*i]>x[2*i+1]:
        swap(x,2*i,2*i+1)

global_min = min( x[0], x[2], ...) # n/2 comparisons
global_max = max( x[1], x[3], ...) # n/2 comparisons

Note that the above solution changes the array. Alternate solution:

Initialize min and max
For i = 0 to n/2:
    if x[2*i]<x[2*i+1]:
        if x[2*i]< min:
            min = x[2*i]
        if x[2*i+1]> max:
            max = x[2*i+1]
    else:
        if x[2*i+1]< min:
            min = x[2*i+1]
        if x[2*i]> max:
            max = x[2*i]