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