新・アルゴリズムとデータ構造入門 Java編15:二分探索の詳細

import java.util.function.Function;

public class Main {
    static int binarySearch(int l_init, int r_init, int precision, Function<Integer, Boolean> f) {
        // 初期値
        int l = l_init;
        int r = r_init;

        // 終了条件
        while (r - l > precision) {
            // 中間値の計算
            int m = (l + r) / 2;

            if (f.apply(m) == false) {
                l = m;
            } else {
                r = m;
            }
        }
        // r (true 側) を返す
        return r;
    }

    static Boolean f(int x) {
        int[] a = {2, 3, 5, 7, 11, 13, 17, 19, 23};
        return a[x] >= 10;
    }

    public static void main(String[] args) {
        // 初期値と精度の設定
        System.out.println(binarySearch(-1, 9, 1, Main::f));
    }
}

import java.util.function.Function;

public class Main {
    static int binarySearch(int l_init, int r_init, int precision, Function<Integer, Boolean> f) {
        // 初期値
        int l = l_init;
        int r = r_init;

        // 終了条件
        while (r - l > precision) {
            // 中間値の計算
            int m = (l + r) / 2;

            if (f.apply(m) == false) {
                l = m;
            } else {
                r = m;
            }
        }
        // r (true 側) を返す
        return r;
    }

    static Boolean f(int x) {
        int[] a = {2, 3, 5, 7, 11, 13, 17, 19, 23};
        return a[x] >= 10;
    }

    public static void main(String[] args) {
        // 初期値と精度の設定
        System.out.println(binarySearch(-1, 9, 1, Main::f));
    }
}

import java.util.function.Function;
import java.util.Scanner;
import java.lang.Math;

public class Main {
	static int count = 0;

	static double binarySearch(double l_init, double r_init, double precision,
			Function<Double, Boolean> f) {
		double l = l_init;
		double r = r_init;

		// 条件を変更
		while (r - l > precision) {
			// 中間値の計算方法を変更
			double m = (l + r) / 2;

			if (f.apply(m) == false) {
				l = m;
			} else {
				r = m;
			}
			count++;
		}
		return r;
	}

	static int a, b;

	static Boolean f(double x) {
		return a * x + Math.sin(x) > b;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		double x = binarySearch(1, 100, 0.0001, Main::f);
		System.out.printf("%.3f\n", x);
		System.err.println(count);
	}
}

import java.util.function.Function;
import java.util.Scanner;
import java.lang.Math;

public class Main {
	static int count = 0;

	static double binarySearch(double l_init, double r_init, double precision,
			Function<Double, Boolean> f) {
		double l = l_init;
		double r = r_init;

		// 条件を変更
		while (r - l > precision) {
			// 中間値の計算方法を変更
			double m = (l + r) / 2;

			if (f.apply(m) == false) {
				l = m;
			} else {
				r = m;
			}
			count++;
		}
		return r;
	}

	static int a, b;

	static Boolean f(double x) {
		return a * x + Math.sin(x) > b;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		double x = binarySearch(1, 100, 0.0001, Main::f);
		System.out.printf("%.3f\n", x);
		System.err.println(count);
	}
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「相対誤差による高速化」

右側のコードエリアには、絶対誤差を基準にして、ある関数が一定の値を超える境界を求める二分探索プログラムが実装されています。
このコードの終了条件や、中間値の計算方法を変更して、より高速に計算するプログラムを作成してみましょう。
なお、このコードでは実行時エラーのところに合計ループ回数が出力されるようにしてあります。
また、この演習課題はデフォルトコードでも正解になりますが、より高速に計算するプログラムを作成した場合でも正解になるように取り組んでみてください。