001package algs14; 002import java.util.Arrays; 003import stdlib.*; 004/* *********************************************************************** 005 * Compilation: javac BitonicMax.java 006 * Execution: java BitonicMax N 007 * 008 * Find the maximum in a bitonic array (strictly increasing, then strictly 009 * decreasing) of size N in log N time. 010 * 011 * % java BitonicMax N 012 * 013 *************************************************************************/ 014 015public class XBitonicMax { 016 017 // create a bitonic array of size N. First element is always 0 018 public static int[] bitonic(int N) { 019 if (N < 3) throw new IllegalArgumentException(); 020 021 int[] a = new int[N]; 022 int mid = StdRandom.uniform(N); 023 024 for (int i = 1; i < mid; i++) a[i] = a[i-1] + StdRandom.uniform(9) + 1; // increasing 025 if (mid != 0) a[mid] = a[mid-1] + StdRandom.uniform(10) - 5; // increasing or decreasing 026 for (int i = mid+1; i < N; i++) a[i] = a[i-1] - StdRandom.uniform(9) - 1; // decreasing 027 return a; 028 } 029 030 // find the index of the maximum in a bitonic subarray a[lo..hi] 031 public static int max(int[] a, int lo, int hi) { 032 if (hi == lo) return hi; 033 int mid = lo + (hi - lo) / 2; 034 if (a[mid] < a[mid + 1]) return max(a, mid+1, hi); 035 if (a[mid] > a[mid + 1]) return max(a, lo, mid); 036 else return mid; 037 } 038 039 040 041 public static void main(String[] args) { 042 args = new String[] { "3" }; 043 int N = Integer.parseInt(args[0]); 044 int[] a = bitonic(N); 045 StdOut.println("a = " + Arrays.toString (a)); 046 StdOut.println("max = " + a[max(a, 0, N-1)]); 047 } 048} 049