Correct algorithm to find the farthest numbers in an array in linear time?

Question

Is this a correct algorithm to find the two furthest numbers in an array in linear time?

lowest = INT_MAX
highest = 0
for i in inputarray:
     if (i < lowest) lowest = i
     if (i > highest) highest = i
return (lowest, highest) 

I would call it linear time as it does only one pass over the array.

Answer 1

Yes, your algorithm is in linear time, but as correctly pointed out by @Tushar with 2N comparisons.

First, here goes an adaptation of your algorithm, with fewer comparisons and without building the array of [0, n].

def minmax(inputarray):
    lowest = highest = inputarray[0]
    for i in inputarray:
        if (i < lowest):
            lowest = i
        elif (i > highest):
        highest = i
    return (lowest, highest) 

Then, this is an implementation with 1.5N comparisons and with generators so that we are cheap on memory:

from itertools import islice, izip

def minmax(inputarray):
    mid = len(inputarray) / 2
    lowest = highest = inputarray[mid]
    iseven = mid * 2 == len(inputarray)
    left = islice(inputarray, 0, mid)
    right = islice(inputarray, mid + (0 if iseven else 1), len(inputarray))
    for x, y in izip(left, right):
        l, h = (x, y) if x < y else (y, x)
        if l < lowest:
            lowest = l
        if h > highest:
            highest = h
    return (lowest, highest)

Result (the latter algorithm):

>>> minmax([0., -1.2, -33, 25, 1.4, 0])
(-33, 25)
>>> minmax([0., -1.2, -33, 25, 1.4])
(-33, 25)

Answer 2

The approach that you have followed in your algorithm has 2*n number of comparisons (n is the total number of numbers in your array) as you are iterating over the array and compare each number with lowest and highest and then updating lowest or highest number accordingly.

You can make this algorithm slightly better by comparing numbers in pair and then compare larger number in pair with highest and smaller number with lowest. So, that for one number pair you end up in doing 3 comparisons. So, total number of comparisons would be 1.5*n.

You can find more details on : FindMinMax

Answer 3

You could also just sort the array, and then pick the first and last numbers. That takes NlogN time. Cheapest on programmer time for sure :)