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

Programming

Share

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

### 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)`.

Share