ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】二分探索を汎用的に使えるようにする

【Java】二分探索を汎用的に使えるようにする  


 色々な問題を解いていると、二分探索で簡単に解けるものもあるのだが、毎回同じコードを書くのは少しメンドイね。なので探索部分と条件判別部分を分け、探索絞り込み方向だけを返すインターフェイスを作って、二分探索のコードを使いまわす方法をやってみよう。条件だけ変えて、色々な値を二分探索でテストしてみたいときにも良いだろう。

 まずは、毎回入れ替える条件部分のコードを独立させるためのインターフェイスを作る。値を1つ受け取り、真偽値を返すだけのシンプルなものだ。

●二分探索の条件関数用インターフェイス
public interface ICondition {
boolean condition(double x);
}

※JDK1.8 以降なら、インタフェース「DoublePredicate」の「test()」メソッドを使うのも良い。


 次に、二分探索の本体を作る。関数は実数と整数用で2つ用意した。特に実数は条件によっては無限ループしかねないので、単純回数分のループとなっている。実数演算はどうしても誤差が出るのだが、精度としてはこれで十分だろう。

●値の二分探索関数(実数, 整数用の2つ)
/**<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;
}

※ IConditionインターフェイスはそれぞれ型によって、IntPredicate, LongPredicate, DoublePredicate (JDK1.8 以降) などに置き換えても良い(もちろん、引数の異なった複数の関数を書く必要があるが…)。


 インターフェイスを噛ませて作る関数「boolean condition(double x)」の戻値は、「解がもっと大きな値をとる場合 true、解がもっと小さな値をとる場合 false」となるように作る。これは二分探索の探索方向(絞り込む範囲)を定めるためのものだ。これは図解でのイメージと、実際の問題を例にあげて理解してみよう。


●二分探索は mid を基準に、探索範囲を半分にしながら、x を絞り込む

●問題例1
 長さのリストが A であるような N 本の紐があります。これらの紐を切って、同じ長さの紐を K 本つくるときの最長の長さを求めなさい。(参考) アリ本 P.129

●解答例1 (実数での二分探索)
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() 関数は省略
}

2.005

 上の例では、条件判別の関数「boolean condition(double x)」を匿名クラスで作っているが、メインコードのクラスに implements して使っても良い。

●解答例1b (インターフェイスを implements して使う)
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() 関数は省略
}

2.005


 方程式の解などでも構わない。ただし式が単調増加(単調減少)のものに限る。

●問題例2
 x >= 0 のとき、x3 + x2 + x = 1 の解 x を求めなさい。(参考) ヒョウ本 P.253 (解答例はない)

●解答例2 (方程式の解を求める二分探索)
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() 関数は省略

0.5436890126920764


 もう少し複雑な問題もやってみよう。

●問題例3
 自動車ローンは固定利率で計算されます。ローンの残高は表示価格から始まり、各月において、月々の利子が残高に加わります。月々の利率は年間利率の 1/12 です。そして、支払い分が残高から引かれます。ローン初期残高(表示価格)を price、月々の支払額を monthlyPayment、ローン回数を loanTerm とするとき、年間利率(%) を求めなさい。(参考) ヒョウ本 P.257

●解答例3 (ローン利率を求める二分探索)
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() 関数は省略
}

9.56205462458368


 最後に整数の二分探索の関数も使ってみよう。

●問題例4
 直線上に並ぶ、位置リストが A であるような N 個の小屋があります。M 頭の牛を、他の小屋とできるだけ離れるように入れるとき、最も近い2頭の間隔を最大化しなさい。(参考) アリ本 P.131

●解答例4 (整数での二分探索)
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() 関数は省略
}

8


 二分探索は絞り込む方向だけ間違えなければ、だいたい近い答えが出る。もし明らかにおかしい値が出たら、とりあえず不等号を反転してみると良い(上限または下限値が出たら、方向間違いと疑ってみる)。あとは探索対象が単調増加であることを確かめよう。上手くいけば、全探索より何倍も速くなるので、考慮してみる価値はあるだろう。


(関連記事)
【Java】lower_bound(), upper_bound() 関数を作る


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 二分探索  アルゴリズム  練習問題 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/195-9a4e2fb1
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop