Find max and min using least operations

© Parineeth M R

Question 39. Find the maximum and minimum elements in an array using the least number of comparisons


In the simple approach, we will compare each element of the array with the maximum value and minimum value obtained so far. So for every element, we need 2 comparisons.

In the efficient approach, we pick all pairs of consecutive numbers in the array and first compare the numbers within each pair. Then we compare the highest in the pair with the maximum value and the lowest in the pair with the minimum value. So we need 3 comparisons for 2 elements instead of 4 comparisons needed by the simple approach.

Since we will be picking pairs of consecutive numbers, if we have odd number of elements in the array, the last element will be left unpaired. To avoid this problem, if we have odd elements, we will initialize the max value and the min value to the first element in the array and then go on picking pairs of numbers from the second element onwards.

C/C++


/*a:input array 
length: number of elements in array a
min_value: the minimum value is returned here
max_value: the maximum value is returned here*/
void find_min_max(int a[], int length, int *min_value, int *max_value) {
	int i = 0;
	*max_value = MIN_INT;
	*min_value = MAX_INT;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		max_value and min_value with a[0]*/
		*max_value = *min_value = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > *max_value) 
				*max_value = a[i];
			if (a[i+1] < *min_value)
				*min_value = a[i+1];
		} else {
			if (a[i] < *min_value)
				*min_value = a[i];
			if (a[i+1] > *max_value)
				*max_value = a[i+1];
		}
	}
}



Java


/*a:input array 
result: the minimum value is returned in result[0] and 
	the maximum value is returned in result[1]*/
public static void findMinMax(int[] a, int[] result) {
	int length = a.length;
	int maxValue = MIN_INT;
	int minValue = MAX_INT;
	int i = 0;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		maxValue and minValue with a[0]*/
		maxValue = minValue = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > maxValue) 
				maxValue = a[i];
			if (a[i+1] < minValue)
				minValue = a[i+1];
		} else {
			if (a[i] < minValue)
				minValue = a[i];
			if (a[i+1] > maxValue)
				maxValue = a[i+1];
		}
	}
	result[0] = minValue;
	result[1] = maxValue;
}




Python


#a: input list 
#Returns: the minimum value and maximum value in list are returned
def find_min_max(a) :
	length = len(a)
	max_value = MIN_INT
	min_value = MAX_INT

	i = 0
	if (length % 2 == 1) :
		#If there are odd number of elements, then initialize 
		#max_value and min_value with a[0]
		max_value = min_value = a[0]
		i = 1
	
	while ( i < length ) :
		if (a[i] > a[i+1]) :
			if (a[i] > max_value) :
				max_value = a[i]
			if (a[i+1] < min_value):
				min_value = a[i+1]
		else :
			if (a[i] < min_value):
				min_value = a[i]
			if (a[i+1] > max_value):
				max_value = a[i+1]
		
		i += 2

	return min_value, max_value