CareerCup

If the question is really just to find the min and max in a[25],...,a[75], I don't see the point of specifying the start and end locations instead of just finding the min and max in the whole array. I think we need some clarification.

Anyway, if it is really just to find the min and max, here is a slightly better way to do it:

public void findMinMax(int[] array, int start, int end) {
	if (start < 0 || end >= array.length || start > end) 
		System.out.println("Invalid inputs");
	else {
		int tmpMin, tmpMax;
		int min = end;
		int max = end;
		// for loop checks even number of entries starting from array[start], 
		// up to array[end] or array[end-1], depending if (end-start+1)%2==0 or not
		for (int i = start; i < end; i+=2) {
			if (array[i] <= array[i+1]) {
				tmpMin = i;
				tmpMax = i+1;
			}
			else { // array[i] > array[i+1]
				tmpMin = i+1;
				tmpMax = i;
			}
			min = ( array[min] <= array[tmpMin] ) ? min : tmpMin;
			max = ( array[max] >= array[tmpMax] ) ? max : tmpMax;
		}
		System.out.println("Min = " + Integer.toString(array[min]) + " at index " + Integer.toString(min));
		System.out.println("Max = " + Integer.toString(array[max]) + " at index " + Integer.toString(max));
	}
}

It takes 3 comparisons for every 2 array entries, while the naive solution takes 2 comparisons for every entry.

I agree with you. My mistake I meant

min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;

sorry about that.

I don't see the need to use any sorting technique.... We could just start the index from 25 and scan up to 75 and simultaneously find max and min and this is 0(n)....one might argue tree is better but there's an overhead constructing the tree itself so simple scan will suffice...

What about a merge sort in O (n log n) from index 25 to 75. so that Min = a[25] and Max = a[75].

mergeSort(a,25,75);
	int min = a[25];
	int max = a[75];

In case we cannot modify the array, we can iterate from a[25] to a[75] and keep track of min and max

Complexity O (n) where n = 75 - 25 ;

int min = Integer.MIN_VALUE;
 	int max = Integer.MAX_VALUE;
 	for(int i = 25; i <= 75; i++){
		if( array[i] < min) min = array[i];
		if(array[i] > max) max = array[i];
	}

Another option will be:
A min heap and a max heap out of the range of the array. in O (n/2) each

There are many solutions to the problem. I wonder why they were asked an specific range, 100 elements is still a small size for that range.

Any more ideas?

Segment Trees if the queries is too high.. or just do a min,max

#include "stdio.h"

void printMinMaxInRange(int start, int end, int array[])
{
	int i = 0;
	int min = end;
	int max = start;
	while (i <= ((end - start) / 2))
	{
		if (array[i+start] > array[max])
			max = i + start;
		if (array[end - i] > array[max])
			max = end - i;
		if (array[i+start] < array[min])
			min = i + start;
		if (array[end - i] < array[min])
			min = end - i;
		i++;
	}
	printf("max %d at index %d\nmin %d at index %d\n",
		array[max],max,array[min],min);
}


int main(int argc, char *argv[])
{
	srand(time(NULL));
	int a[101];
	int i = 1;
	while (i < 101)
	{
		a[i] = rand() % 1000;
		i++;
	}
	printMinMaxInRange(25,75,a);
}