算法Sedgewick第四版-第1章基础-1.4 Analysis of Algorithms-006BitonicMax

 1 package algorithms.analysis14;
 2 
 3 import algorithms.util.StdOut;
 4 import algorithms.util.StdRandom;
 5 
 6 /******************************************************************************
 7  *  Compilation:  javac BitonicMax.java
 8  *  Execution:    java BitonicMax N 
 9  *  Dependencies: StdOut.java
10  *
11  *  Find the maximum in a bitonic array (strictly increasing, then strictly
12  *  decreasing) of size N in log N time.
13  * 
14  *  % java BitonicMax N
15  *
16  ******************************************************************************/
17 
18 
19 public class BitonicMax {
20 
21     // create a bitonic array of size N
22     public static int[] bitonic(int N) {
23         int mid = StdRandom.uniform(N);
24         int[] a = new int[N];
25         for (int i = 1; i < mid; i++) {
26             a[i] = a[i-1] + 1 + StdRandom.uniform(9);
27         }
28 
29         if (mid > 0) a[mid] = a[mid-1] + StdRandom.uniform(10) - 5;
30 
31         for (int i = mid + 1; i < N; i++) {
32             a[i] = a[i-1] - 1 - StdRandom.uniform(9);
33         }
34 
35         for (int i = 0; i < N; i++) {
36             StdOut.println(a[i]);
37         }
38         return a;
39     } 
40 
41     // find the index of the maximum in a bitonic subarray a[lo..hi]
42     public static int max(int[] a, int lo, int hi) {
43         if (hi == lo) return hi;
44         int mid = lo + (hi - lo) / 2;
45         if (a[mid] < a[mid + 1]) return max(a, mid+1, hi);
46         if (a[mid] > a[mid + 1]) return max(a, lo, mid);
47         else return mid;
48     } 
49 
50 
51 
52     public static void main(String[] args) {
53 
54         int N = Integer.parseInt(args[0]);
55         int[] a = bitonic(N);
56         StdOut.println("max = " + a[max(a, 0, N-1)]);
57     }
58 }