Find the minimum and maximum number in an array using Tournament Method

In this programming tutorial we will find the minimum and maximum element of an array using Tournament Method.

Related: Find the minimum and maximum number in an array

Problem statement

For the given array of integer values find the minimum and maximum value. Note! There will always be at least 1 number in the array. The numbers can be negative, zero, positive and can repeat.

Lets say we are given the following array of integer values.

[1, 2, 4, 6, 5, 3]

And we have to find the min and max values.

Solution

Tournament method finds the min and max value by dividing the array into sub-arrays till min-max is found for the sub-arrays. Then from the min-max of those sub-arrays we find the min-max of the full array. Divide and Conquer.

To find the minimum and maximum values using Tournament method we perform the following steps.

Steps:

1. Set the start index to the first element of the array.
2. Set the end index to the last element of the array.
3. If start is equal to end then there is only one item in the array and it is the both the minimum and the maximum value.
4. If end - start = 1 then there are two items in the array. Compare and find the min and max values.
5. If there are more items in the array then find the middle index.
   Where, middle = floor((start + end) / 2)
   This divides the array into two parts.
   Left half from index start to middle.
   Right half from index middle+1 to end.
6. We recursively go through step 3 to 5 till we end up with a pair of min and max values.

Code

Python

def min_max(array, start, end):
    # only 1 element in the array
    if start == end:
        return (array[start], array[end])

    # 2 elments in the array
    elif end - start == 1:
        min_number = min(array[start], array[end])
        max_number = max(array[start], array[end])
        return (min_number, max_number)

    # more than 2 elements in the array
    else:
        middle = int(start + end) / 2
        min_num1, max_num1 = min_max(array, start, middle)
        min_num2, max_num2 = min_max(array, middle + 1, end)

    return (min(min_num1, min_num2), max(max_num1, max_num2))

numbers = [1, 2, 4, 5, 6, 3]
start = 0
end = len(numbers) - 1
min_number, max_number = min_max(numbers, start, end)

assert min_number == 1
assert max_number == 6

print('min', min_number, 'max', max_number)

Output

'min', 1, 'max', 6

Time complexity

Time complexity of this is O(n).