package search;

public class BinarySearch {

    // Contract
    // Pred: exists such index "i" that values[i] <= x
    //       and array "values" is sorted by non-increase
    // Post: R = min index "i" that values[i] <= x
    public static int iterativeBinarySearch(int x, int[] values) {
        // R is in (-1, values.length - 1]
        int l = -1, r = values.length - 1;
        // R is in (l, r]
        while (r - l > 1) {
            // R is in (l, r] && r - l > 1
            int m = (l + r) / 2;
            // (R is in (l, m] || R is in (m, r]) && r - l > 1 && l < m < r
            if (values[m] <= x) {
                // values[m] <= x && R is in (l, m] && r - l > 1 && l < m < r
                r = m;
                // R is in (l, r]
            } else {
                // values[m] > x && R is in (m, r] && r - l > 1 && l < m < r
                l = m;
                // R is in (l, r]
            }
            // R is in (l, r]
        }
        // R is in (l, r] && r - l == 1 && R = r
        return r;
    }

    // Contract
    // Pred: R is in (l, r] and r - l >= 1 and array "values" is sorted by non-increase
    // Post: R = min index "i" that values[i] <= x
    public static int recursiveBinarySearch(int x, int l, int r, int[] values) {
        // R is in (l, r] && r - l >= 1
        if (r - l == 1) {
            // R is in (l, r] && r - l == 1 && R = r;
            return r;
        }
        // R is in (l, r] && r - l > 1
        int m = (l + r) / 2;
        // (R is in (l, m] || R is in (m, r]) && r - l > 1 && l < m < r
        if (values[m] <= x) {
            // values[m] <= x && R is in (l, m] && r - l > 1 && l < m < r
            return recursiveBinarySearch(x, l, m, values);
        } else {
            // values[m] > x && R is in (m, r] && r - l > 1 && l < m < r
            return recursiveBinarySearch(x, m, r, values);
        }
    }

    // Pred: array "values" is sorted by non-increase
    // Post: valuest.length == 1 -> 0
    //       valuest[valuest.length - 1] > x -> values.length
    //       else R = min index "i" that values[i] <= x
    public static void main(String[] args) {
        if (args.length <= 1) {
            System.out.println(0);
        } else {
            int x = Integer.parseInt(args[0]);
            int[] values = new int[args.length - 1];
            for (int i = 0; i < values.length; i++) {
                values[i] = Integer.parseInt(args[i + 1]);
            }
            if (values[values.length - 1] > x) {
                System.out.println(values.length);
            } else {
                System.out.println(iterativeBinarySearch(x, values));
                //System.out.println(recursiveBinarySearch(x, -1, values.length - 1, values));
            }
        }
    }
}