ヽ｜∵｜ゝ(Fantom) の 開発blog？

public interface ICondition {
    boolean condition(double x);
}

/**<h1>条件にあった値を二分探索で求める(実数)</h1>
 * <p>条件判別関数は、等しいかより値を大きくとるとき = true となる関数を作る。</p>
 * @param low ： 探索範囲下限
 * @param high ： 探索範囲上限
 * @param c ： 条件判別関数インターフェイス
 * @return<b>double</b> ： 探索で見つけた値
 */
public static final double binarySearch(double low, double high, final ICondition c) {
    double mid = 0;
    for (int i = 0; i < 100; i++) {    //無限ループ対策
        mid = (high - low) / 2 + low;    //(low + high) / 2 (オーバーフロー対策)
        if (c.condition(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}


/**<h1>条件にあった値を二分探索で求める(整数)</h1>
 * <p>条件判別関数は、等しいかより値を大きくとるとき = true となる関数を作る。</p>
 * @param low ： 探索範囲下限
 * @param high ： 探索範囲上限
 * @param c ： 条件判別関数インターフェイス
 * @return<b>int</b> ： 探索で見つけた値
 */
public static final int binarySearch(int low, int high, final ICondition c) {
    int mid = 0;
    while (high - low > 1) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (c.condition(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double[] A;   //長さのリスト
    int N;        //リストの要素数
    int K;        //作る本数

    public BinarySearchTest() {
        A = new double[]{8.02, 7.43, 4.57, 5.39};
        N = A.length;
        K = 11;

        double ans = binarySearch(0.0, 1e5, new ICondition() {
            //・長さ x で K より多く切れるとき → もっと x を長くできる = true
            //・長さ x で K より少なく切れるとき → もっと x を短くする = false
            @Override
            public boolean condition(double x) {
                int cnt = 0;
                for (int i = 0; i < N; i++) {
                    cnt += (int)(A[i] / x);    //作れる本数
                }
                return (cnt >= K);
            }
        });

        System.out.println(ans);    //2.005
    }

    //※ binarySearch() 関数は省略
}

public class BinarySearchTest implements ICondition {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double[] A;   //長さのリスト
    int N;        //リストの要素数
    int K;        //作る本数

    public BinarySearchTest() {
        A = new double[]{8.02, 7.43, 4.57, 5.39};
        N = A.length;
        K = 11;

        double ans = binarySearch(0.0, 1e5, this);
        System.out.println(ans);    //2.005
    }

    //・長さ x で K より多く切れるとき → もっと x を長くできる = true
    //・長さ x で K より少なく切れるとき → もっと x を短くする = false
    @Override
    public boolean condition(double x) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            cnt += (int)(A[i] / x);    //作れる本数
        }
        return (cnt >= K);
    }

    //※ binarySearch() 関数は省略
}

double ans = binarySearch(0.0, 1.0, new ICondition() {
    //・x = 0 とすると、f(x) = 0、x = 1 とすると、f(x) = 3 から、x = 0.0～1.0 となる。
    //・f(x) の解が 1 以下のとき x はもっと大きい = true
    //・f(x) の解が 1 より上のとき x はもっと小さい = false
    @Override
    public boolean condition(double x) {
        return (x * x * x + x * x + x <= 1.0);
    }
});

System.out.println(ans);    //0.5436890126920764

//※ メインコード, binarySearch() 関数は省略

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    double price;            //ローン初期残高
    double monthlyPayment;   //月々の支払額
    int loanTerm;            //ローン回数

    public BinarySearchTest() {
        price = 2000;
        monthlyPayment = 510;
        loanTerm = 4;

        double ans = binarySearch(0.0, 100.0, new ICondition() {
            //・残高がマイナスになる → 利率を大きくする = true
            //・残高がプラスになる → 利率を小さくする = false
            @Override
            public boolean condition(double x) {
                double balance = price;
                for (int i = 0; i < loanTerm; i++) {
                    balance *= x / 1200.0 + 1.0;    //月々の利率
                    balance -= monthlyPayment;
                }
                return (balance <= 0);
            }
        });

        System.out.println(ans);    //9.56205462458368 (%) (※誤差あり)
    }

    //※ binarySearch() 関数は省略
}

public class BinarySearchTest {
    public static void main(String[] args) throws Exception {
        new BinarySearchTest();
    }

    int[] A;      //小屋の位置リスト
    int N;        //リストの要素数
    int M;        //配置する牛の数

    public BinarySearchTest() {
        A = new int[]{1, 3, 4, 6, 7, 10, 12, 15, 18, 20, 22, 23, 25, 27};
        N = A.length;
        M = 4;

        int ans = binarySearch(0, A[N - 1], new ICondition() {
            //・間隔 x で M 頭の牛が全て収まるとき → もっと x を大きくできる = true
            //・間隔 x で M 頭の牛が収まらないとき → もっと x を小さくする = false
            @Override
            public boolean condition(double x) {
                int now = 0;
                for (int i = 1; i < M; i++) {
                    int next = now + 1;
                    while (next < N && A[next] - A[now] < x) {
                        next++;
                    }
                    if (next == N) {
                        return false;    //M 頭まで配置できない
                    }
                    now = next;
                }
                return true;    //M 頭配置できる
            }
        });

        System.out.println(ans);    //8
    }

    //※ binarySearch() 関数は省略
}

/**<h1>指定した値以上の先頭のインデクスを返す</h1>
 * <p>配列要素が０のときは、０が返る。</p>
 * @param arr ： 探索対象配列(単調増加であること)
 * @param value ： 探索する値
 * @return<b>int</b> ： 探索した値以上で、先頭になるインデクス
 */
public static final int lowerBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (arr[mid] < value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

/**<h1>指定した値より大きい先頭のインデクスを返す</h1>
 * <p>配列要素が０のときは、０が返る。</p>
 * @param arr ： 探索対象配列(単調増加であること)
 * @param value ： 探索する値
 * @return<b>int</b> ： 探索した値より上で、先頭になるインデクス
 */
public static final int upperBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (arr[mid] <= value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

//メインコード
int[] A = new int[]{5, 1, 3, 5, 10, 7, 4, 9, 2, 8};    //数列
int N = A.length;    //数列の長さ
int S = 15;        //求める和(以上)

static final int INF = 100000000;

System.out.println(solve());    //答え


//二分探索での解法
int solve() {
    int ans = INF;
    int[] sum = new int[N + 1];

    for (int i = 0; i < N; i++) {
        sum[i + 1] = sum[i] + A[i];
    }

    for (int i = 0; S <= sum[N] - sum[i]; i++) {
        int t = lowerBound(sum, sum[i] + S);
        ans = Math.min(ans, t - i);
    }

    return (ans == INF ? 0 : ans);
}

int[] data = {1, 2, 2, 3, 3, 3, 4, 5, 5, 6};     //ソート済みであること
int v = 3;    //検索する値
int k = upperBound(data, v) - lowerBound(data, v);    //差分が個数になる(ないとき=0)
System.out.println(k);

/**<h1>指定した値と同じか後ろにある、先頭のインデクスを返す</h1>
 * <p>配列要素が０のときは、０が返る。</p>
 * @param arr ： 探索対象配列(単調増加/減少であること)
 * @param value ： 探索する値
 * @param comparator ： Comparator<Integer> インターフェイス
 * @return<b>int</b> ： 探索した値と同じか後ろで、先頭になるインデクス
 */
public static final int lowerBound(final int arr[], final int value, final Comparator<Integer> comparator) {
    int low = 0;
    int high = arr.length;
    int mid;
    int cmp;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        cmp = comparator.compare(arr[mid], value);
        if (cmp < 0) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

/**<h1>指定した値より後ろにある、先頭の要素を返す</h1>
 * <p>配列要素が０のときは、０が返る。</p>
 * @param arr ： 探索対象配列(単調増加/減少であること)
 * @param value ： 探索する値
 * @param comparator ： Comparator<Integer> インターフェイス
 * @return<b>int</b> ： 探索した値より後ろで、先頭になるインデクス
 */
public static final int upperBound(final int arr[], final int value, final Comparator<Integer> comparator) {
    int low = 0;
    int high = arr.length;
    int mid;
    int cmp;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        cmp = comparator.compare(arr[mid], value);
        if (cmp <= 0) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}


//メインコード例（A は単調減少の配列）
int ans = lowerBound(A, K, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;    //降順
    }
});