-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathTournamentMethod.java
More file actions
59 lines (49 loc) · 1.41 KB
/
Copy pathTournamentMethod.java
File metadata and controls
59 lines (49 loc) · 1.41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package Array;
/**
* Created by Prashant on 6/12/16.
* Maximum and minimum of an array using minimum number of comparisons
* total number of comparisons is 3/2 n - 2
* https://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/
*/
public class TournamentMethod {
static class MinMax {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
}
public static MinMax minMax(int a[], int l, int r) {
MinMax mm = new MinMax();
if (l == r) {
mm.max = a[l];
mm.min = a[l];
return mm;
}
if (r == l + 1) {
if (a[l] < a[r]) {
mm.min = a[l];
mm.max = a[r];
} else {
mm.max = a[l];
mm.min = a[r];
}
return mm;
}
int mid = (l + r) / 2;
MinMax minMaxL = minMax(a, l, mid);
MinMax minMaxR = minMax(a, mid + 1, r);
if (minMaxL.min < minMaxR.min) {
mm.min = minMaxL.min;
} else {
mm.min = minMaxR.min;
}
if (minMaxL.max > minMaxR.max) {
mm.max = minMaxL.max;
} else {
mm.max = minMaxR.max;
}
return mm;
}
public static void main(String[] args) {
int[] a = {1000, 11, 445, 1, 330, 3000};
MinMax mm = minMax(a, 0, a.length - 1);
System.out.print(mm.min + " " + mm.max);
}
}