package algs14;
import java.util.Arrays;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac BitonicMax.java
 *  Execution:    java BitonicMax N
 *
 *  Find the maximum in a bitonic array (strictly increasing, then strictly
 *  decreasing) of size N in log N time.
 *
 *  % java BitonicMax N
 *
 *************************************************************************/

public class XBitonicMax {

  // create a bitonic array of size N.  First element is always 0
  public static int[] bitonic(int N) {
    if (N < 3) throw new IllegalArgumentException();

    int[] a = new int[N];
    int mid = StdRandom.uniform(N);

    for (int i = 1;   i < mid; i++) a[i] = a[i-1]   + StdRandom.uniform(9) + 1;  // increasing
    if (mid != 0)                 a[mid] = a[mid-1] + StdRandom.uniform(10) - 5; // increasing or decreasing
    for (int i = mid+1; i < N; i++) a[i] = a[i-1]   - StdRandom.uniform(9) - 1;  // decreasing
    return a;
  }

  // find the index of the maximum in a bitonic subarray a[lo..hi]
  public static int max(int[] a, int lo, int hi) {
    if (hi == lo) return hi;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[mid + 1]) return max(a, mid+1, hi);
    if (a[mid] > a[mid + 1]) return max(a, lo, mid);
    else return mid;
  }



  public static void main(String[] args) {
    args = new String[] { "3" };
    int N = Integer.parseInt(args[0]);
    int[] a = bitonic(N);
    StdOut.println("a = " + Arrays.toString (a));
    StdOut.println("max = " + a[max(a, 0, N-1)]);
  }
}