# Maximum and minimum of an array M3

METHOD 3 (Compare in Pairs)
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For rest of the elements, pick them in pairs and compare their
maximum and minimum with max and min respectively.

`// C++ program of above implementation`

`#include<iostream>`

`using` `namespace` `std;`

`// Structure is used to return`

`// two values from minMax()`

`struct` `Pair`

`{`

` ` `int` `min;`

` ` `int` `max;`

`};`

`struct` `Pair getMinMax(` `int` `arr[], ` `int` `n)`

`{`

` ` `struct` `Pair minmax; `

` ` `int` `i;`

` `

` ` `// If array has even number of elements`

` ` `// then initialize the first two elements`

` ` `// as minimum and maximum`

` ` `if` `(n % 2 == 0)`

` ` `{`

` ` `if` `(arr[0] > arr[1]) `

` ` `{`

` ` `minmax.max = arr[0];`

` ` `minmax.min = arr[1];`

` ` `}`

` ` `else`

` ` `{`

` ` `minmax.min = arr[0];`

` ` `minmax.max = arr[1];`

` ` `}`

` `

` ` `// Set the starting index for loop`

` ` `i = 2;`

` ` `}`

` `

` ` `// If array has odd number of elements`

` ` `// then initialize the first element as`

` ` `// minimum and maximum`

` ` `else`

` ` `{`

` ` `minmax.min = arr[0];`

` ` `minmax.max = arr[0];`

` `

` ` `// Set the starting index for loop`

` ` `i = 1;`

` ` `}`

` `

` ` `// In the while loop, pick elements in`

` ` `// pair and compare the pair with max`

` ` `// and min so far`

` ` `while` `(i < n - 1)`

` ` `{ `

` ` `if` `(arr[i] > arr[i + 1]) `

` ` `{`

` ` `if` `(arr[i] > minmax.max) `

` ` `minmax.max = arr[i];`

` `

` ` `if` `(arr[i + 1] < minmax.min) `

` ` `minmax.min = arr[i + 1]; `

` ` `}`

` ` `else`

` ` `{`

` ` `if` `(arr[i + 1] > minmax.max) `

` ` `minmax.max = arr[i + 1];`

` `

` ` `if` `(arr[i] < minmax.min) `

` ` `minmax.min = arr[i]; `

` ` `}`

` `

` ` `// Increment the index by 2 as`

` ` `// two elements are processed in loop`

` ` `i += 2;`

` ` `} `

` ` `return` `minmax;`

`}`

`// Driver code`

`int` `main()`

`{`

` ` `int` `arr[] = { 1000, 11, 445,`

` ` `1, 330, 3000 };`

` ` `int` `arr_size = 6;`

` `

` ` `Pair minmax = getMinMax(arr, arr_size);`

` `

` ` `cout << ` `"nMinimum element is "`

` ` `<< minmax.min << endl;`

` ` `cout << ` `"nMaximum element is "`

` ` `<< minmax.max;`

` `

` ` `return` `0;`

`}`

Output:

Minimum element is 1 Maximum element is 3000

Time Complexity: O(n)

Total number of comparisons: Different for even and odd n, see below:

If n is odd: 3*(n-1)/2 If n is even: 1 Initial comparison for initializing min and max, and 3(n-2)/2 comparisons for rest of the elements = 1 + 3*(n-2)/2 = 3n/2 -2

Second and third approaches make the equal number of comparisons when n is a power of 2.
In general, method 3 seems to be the best.
Please write comments if you find any bug in the above programs/algorithms or a better way to solve the same problem.