Programming
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
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.
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:
start
end
end - start = 1
middle
middle = floor((start + end) / 2)
middle+1
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)
'min', 1, 'max', 6
Time complexity of this is O(n).
O(n)