Let's say I have an Array of numbers: [2,3,3,4,2,2,5,6,7,2]
What is the best way to find the minimum or maximum value in that Array?
Right now, to get the maximum, I am looping through the Array, and resetting a variable to the value if it is greater than the existing value:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = 0;
for each (var num:Number in myArray)
{
if (num > maxValue)
maxValue = num;
}
This just doesn't seem like the best performing way to do this (I try to avoid loops whenever possible).
This question is related to
algorithm
actionscript-3
apache-flex
actionscript
complexity-theory
If you want to find both the min and max at the same time, the loop can be modified as follows:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
This should get achieve O(n) timing.
Unless the array is sorted, that's the best you're going to get. If it is sorted, just take the first and last elements.
Of course, if it's not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That's O(N*Log N) total. A simple scan once through is only O(N).
If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.
Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.
The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)
The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).
This depends on real world application requirements.
If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.
However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.
The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.
For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.
Nick.
Unless the array is sorted, that's the best you're going to get. If it is sorted, just take the first and last elements.
Of course, if it's not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That's O(N*Log N) total. A simple scan once through is only O(N).
If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.
If you want to find both the min and max at the same time, the loop can be modified as follows:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
This should get achieve O(n) timing.
If you are building the array once and want to find the maximum just once, iterating is the best you can do.
When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.
To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.
Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large
If you are building the array once and want to find the maximum just once, iterating is the best you can do.
When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.
To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.
If you want to find both the min and max at the same time, the loop can be modified as follows:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
This should get achieve O(n) timing.
Algorithm MaxMin(first, last, max, min)
//This algorithm stores the highest and lowest element
//Values of the global array A in the global variables max and min
//tmax and tmin are temporary global variables
{
if (first==last) //Sub-array contains single element
{
max=A[first];
min=A[first];
}
else if(first+1==last) //Sub-array contains two elements
{
if(A[first]<A[Last])
{
max=a[last]; //Second element is largest
min=a[first]; //First element is smallest
}
else
{
max=a[first]; //First element is Largest
min=a[last]; //Second element is smallest
}
}
else
//sub-array contains more than two elements
{
//Hence partition the sub-array into smaller sub-array
mid=(first+last)/2;
//Recursively solve the sub-array
MaxMin(first,mid,max,min);
MaxMin(mid+1,last,tmax,tmin);
if(max<tmax)
{
max=tmax;
}
if(min>tmin)
{
min=tmin;
}
}
}
There are a number of ways this can be done.
How to find max. and min. in array using minimum comparisons?
If you are really paranoid about speed, runtime & number of comparisons, also refer to http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/
Math.max() is actually as3 code compiled to AVM2 opcodes, and as such is not more "native" than any other as3 code. As a consequence, it is not necessarily the fastest implementation.
Actually, given that it works on Array type, it is slower than carefully written code usign Vector:
I did a quick benchmark comparison of several naive Vector and Array implementations of Math.max, using gskinner's PerformanceTest (Vector and Array being filled with identical random Numbers). The fastest Vector implementation appeared to be more than 3x faster than Math.max with recent AIR SDK/release player (flash player WIN 14,0,0,122 RELEASE, compiled with AIR SDK 14):
average 3.5 ms for 1,000,000 values, compared to Math.max() average of 11ms :
function max(values:Vector.<Number>):Number
{
var max:Number = Number.MIN_VALUE;
var length:uint = values.length;
for (var i:uint = 0; i < length ; ++i)
if (values[i] > max)
max = values[i];
return max;
}
Conclusion is that if you are concerned by performance, you should use Vector over Array anywhere you can in the first place, and not always rely on default implementations, especially when they force the use of Array
PS:same implementation with a for each() loop is 12x slower ...!
If you are building the array once and want to find the maximum just once, iterating is the best you can do.
When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.
To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.
After reading everyone's comments (thank you for your interest), I found that the "best" way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
This also works for an Array of Objects - you simply use the Array.sortOn() function and specify a property:
// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;
I hope this helps someone else someday!
Find max values from a array Let's see how to obtain min, max values by using a single funtion
public void findMaxValue(){
int[] my_array = {1,2,,6,5,8,3,9,0,23};
int max = my_array[0];
for(int i=1; i<my_array.length; i++)
{
if(my_array[i] > max)
max = my_array[i];
}
return max;
}
same thing can do for find min value
If you want to find both the min and max at the same time, the loop can be modified as follows:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
This should get achieve O(n) timing.
There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.
Amazed no-one mentioned parallelism here.
If you got really a huge array, you can use parallel-for, on sub ranges. In the end compare all sub-ranges. But parallelism comes width some penalty too, so this would not optimize on small arrays. However if you got huge datasets it starts to make sense, and you get a time division reduction nearing the amount of threads performing the test.
There are a number of ways this can be done.
How to find max. and min. in array using minimum comparisons?
If you are really paranoid about speed, runtime & number of comparisons, also refer to http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/
This depends on real world application requirements.
If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.
However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.
The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.
For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.
Nick.
There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.
Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.
The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)
The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).
Amazed no-one mentioned parallelism here.
If you got really a huge array, you can use parallel-for, on sub ranges. In the end compare all sub-ranges. But parallelism comes width some penalty too, so this would not optimize on small arrays. However if you got huge datasets it starts to make sense, and you get a time division reduction nearing the amount of threads performing the test.
Below is Solution with o(n):-
public static void findMaxAndMinValue(int A[]){
int min =0, max = 0;
if(A[0] > A[1] ){
min = A[1];
max = A[0];
}else{
max = A[1];
min = A[0];
}
for(int i = 2;i<A.length ;i++){
if(A[i] > max){
max = A[i];
}
if(min > A[i]){
min = A[i];
}
}
System.out.println("Maxinum Value is "+min+" & Minimum Value is "+max);
}
If you are building the array once and want to find the maximum just once, iterating is the best you can do.
When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.
To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.
After reading everyone's comments (thank you for your interest), I found that the "best" way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
This also works for an Array of Objects - you simply use the Array.sortOn() function and specify a property:
// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;
I hope this helps someone else someday!
Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large
There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.
Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.
The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)
The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).
Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large
You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.
There isn't any reliable way to get the minimum/maximum without testing every value. You don't want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.
You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.
Shortest way :
Math.min.apply(null,array); //this will return min value from array
Math.max.apply(null,array); //this will return max value from array
otherway of getting min & max value from array
function maxVal(givenArray):Number
{
var max = givenArray[0];
for (var ma:int = 0; ma<givenArray.length; ma++)
{
if (givenArray[ma] > max)
{
max = givenArray[ma];
}
}
return max;
}
function minVal(givenArray):Number
{
var min = givenArray[0];
for (var mi:int = 0; mi<givenArray.length; mi++)
{
if (givenArray[mi] < min)
{
min = givenArray[mi];
}
}
return min;
}
As you can see, the code in both of these functions is very similar. The function sets a variable - max (or min) and then runs through the array with a loop, checking each next element. If the next element is higher than the current, set it to max (or min). In the end, return the number.
Depends on what you call "best." From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.
The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn't necessarily faster due to function call overhead).
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
The simplest solution would be to sort and get the first and last item, though it's obviously not the fastest ;)
The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).
After reading everyone's comments (thank you for your interest), I found that the "best" way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
This also works for an Array of Objects - you simply use the Array.sortOn() function and specify a property:
// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;
I hope this helps someone else someday!
Below is Solution with o(n):-
public static void findMaxAndMinValue(int A[]){
int min =0, max = 0;
if(A[0] > A[1] ){
min = A[1];
max = A[0];
}else{
max = A[1];
min = A[0];
}
for(int i = 2;i<A.length ;i++){
if(A[i] > max){
max = A[i];
}
if(min > A[i]){
min = A[i];
}
}
System.out.println("Maxinum Value is "+min+" & Minimum Value is "+max);
}
This depends on real world application requirements.
If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.
However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.
The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.
For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.
Nick.
Shortest way :
Math.min.apply(null,array); //this will return min value from array
Math.max.apply(null,array); //this will return max value from array
otherway of getting min & max value from array
function maxVal(givenArray):Number
{
var max = givenArray[0];
for (var ma:int = 0; ma<givenArray.length; ma++)
{
if (givenArray[ma] > max)
{
max = givenArray[ma];
}
}
return max;
}
function minVal(givenArray):Number
{
var min = givenArray[0];
for (var mi:int = 0; mi<givenArray.length; mi++)
{
if (givenArray[mi] < min)
{
min = givenArray[mi];
}
}
return min;
}
As you can see, the code in both of these functions is very similar. The function sets a variable - max (or min) and then runs through the array with a loop, checking each next element. If the next element is higher than the current, set it to max (or min). In the end, return the number.
If
Then there is an algorithm that finds the min and max in 3n/2 number of comparisons. What one needs to do is process the elements of the array in pairs. The larger of the pair should be compared with the current max and the smaller of the pair should be compared with the current min. Also, one needs take special care if the array contains odd number of elements.
In c++ code (borrowing some code from Mehrdad).
struct MinMax{
int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
MinMax min_max;
int index;
int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
if ( n%2 != 0 ){// if n is odd
min_max.Min = array[start];
min_max.Max = array[start];
index = start + 1;
}
else{// n is even
if ( array[start] < array[start+1] ){
min_max.Min = array[start];
min_max.Max = array[start+1];
}
else{
min_max.Min = array[start+1];
min_max.Max = array[start];
}
index = start + 2;
}
int big, small;
for ( int i = index; i < n-1; i = i+2 ){
if ( array[i] < array[i+1] ){ //one comparison
small = array[i];
big = array[i+1];
}
else{
small = array[i+1];
big = array[i];
}
if ( min_max.Min > small ){ //one comparison
min_max.Min = small;
}
if ( min_max.Max < big ){ //one comparison
min_max.Max = big;
}
}
return min_max;
}
It's very easy to see that the number of comparisons it takes is 3n/2. The loop runs n/2 times and in each iteration 3 comparisons are performed. This is probably the optimum one can achieve. At this moment, I cannot point to a definite source of that. (But, I think I have seen a proof of that somewhere.)
The recursive solution given by Mehrdad above, probably also achieves this minimal number of comparisons (the last line needs to be changed). But with the same number of comparisons an iterative solution will always beat a recursive solution due to overhead in the function call as he mentioned. However, if one only cares about finding min and max of a few numbers (as Eric Belair does), no one will notice any difference in todays computer with any of the approaches above. For a large array, the difference could be significant.
Though this solution and the solution given by Matthew Brubaker has O(n) complexity, in practice one should carefully asses the hidden constants involved. The number of comparisons in his solution is 2n. The speedup gained with the solution with 3n/2 comparisons as opposed to 2n comparisons would be noticeable.
This depends on real world application requirements.
If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.
However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational 'hit' at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.
The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element - giving you an O(1) cost.
For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.
Nick.
You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.
Find max values from a array Let's see how to obtain min, max values by using a single funtion
public void findMaxValue(){
int[] my_array = {1,2,,6,5,8,3,9,0,23};
int max = my_array[0];
for(int i=1; i<my_array.length; i++)
{
if(my_array[i] > max)
max = my_array[i];
}
return max;
}
same thing can do for find min value
You have to loop through the array, no other way to check all elements. Just one correction for the code - if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it's a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.
If
Then there is an algorithm that finds the min and max in 3n/2 number of comparisons. What one needs to do is process the elements of the array in pairs. The larger of the pair should be compared with the current max and the smaller of the pair should be compared with the current min. Also, one needs take special care if the array contains odd number of elements.
In c++ code (borrowing some code from Mehrdad).
struct MinMax{
int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
MinMax min_max;
int index;
int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
if ( n%2 != 0 ){// if n is odd
min_max.Min = array[start];
min_max.Max = array[start];
index = start + 1;
}
else{// n is even
if ( array[start] < array[start+1] ){
min_max.Min = array[start];
min_max.Max = array[start+1];
}
else{
min_max.Min = array[start+1];
min_max.Max = array[start];
}
index = start + 2;
}
int big, small;
for ( int i = index; i < n-1; i = i+2 ){
if ( array[i] < array[i+1] ){ //one comparison
small = array[i];
big = array[i+1];
}
else{
small = array[i+1];
big = array[i];
}
if ( min_max.Min > small ){ //one comparison
min_max.Min = small;
}
if ( min_max.Max < big ){ //one comparison
min_max.Max = big;
}
}
return min_max;
}
It's very easy to see that the number of comparisons it takes is 3n/2. The loop runs n/2 times and in each iteration 3 comparisons are performed. This is probably the optimum one can achieve. At this moment, I cannot point to a definite source of that. (But, I think I have seen a proof of that somewhere.)
The recursive solution given by Mehrdad above, probably also achieves this minimal number of comparisons (the last line needs to be changed). But with the same number of comparisons an iterative solution will always beat a recursive solution due to overhead in the function call as he mentioned. However, if one only cares about finding min and max of a few numbers (as Eric Belair does), no one will notice any difference in todays computer with any of the approaches above. For a large array, the difference could be significant.
Though this solution and the solution given by Matthew Brubaker has O(n) complexity, in practice one should carefully asses the hidden constants involved. The number of comparisons in his solution is 2n. The speedup gained with the solution with 3n/2 comparisons as opposed to 2n comparisons would be noticeable.
Unless the array is sorted, that's the best you're going to get. If it is sorted, just take the first and last elements.
Of course, if it's not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That's O(N*Log N) total. A simple scan once through is only O(N).
If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.
Source: Stackoverflow.com