【Java】二分探索を汎用的に使えるようにする
2015/11/11 Wed [edit]
色々な問題を解いていると、二分探索で簡単に解けるものもあるのだが、毎回同じコードを書くのは少しメンドイね。なので探索部分と条件判別部分を分け、探索絞り込み方向だけを返すインターフェイスを作って、二分探索のコードを使いまわす方法をやってみよう。条件だけ変えて、色々な値を二分探索でテストしてみたいときにも良いだろう。
まずは、毎回入れ替える条件部分のコードを独立させるためのインターフェイスを作る。値を１つ受け取り、真偽値を返すだけのシンプルなものだ。
●二分探索の条件関数用インターフェイス
public interface ICondition {
boolean condition(double x);
}
※JDK1.8 以降なら、インタフェース「DoublePredicate」の「test()」メソッドを使うのも良い。
次に、二分探索の本体を作る。関数は実数と整数用で２つ用意した。特に実数は条件によっては無限ループしかねないので、単純回数分のループとなっている。実数演算はどうしても誤差が出るのだが、精度としてはこれで十分だろう。
●値の二分探索関数（実数, 整数用の２つ)
/**<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 を絞り込む
●問題例１
長さのリストが A であるような N 本の紐があります。これらの紐を切って、同じ長さの紐を K 本つくるときの最長の長さを求めなさい。(参考) アリ本 P.129
●解答例１ (実数での二分探索)
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 して使っても良い。
●解答例１b (インターフェイスを 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
方程式の解などでも構わない。ただし式が単調増加(単調減少)のものに限る。
●問題例２
x >= 0 のとき、x3 + x2 + x = 1 の解 x を求めなさい。(参考) ヒョウ本 P.253 (解答例はない)
●解答例２ (方程式の解を求める二分探索)
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
もう少し複雑な問題もやってみよう。
●問題例３
自動車ローンは固定利率で計算されます。ローンの残高は表示価格から始まり、各月において、月々の利子が残高に加わります。月々の利率は年間利率の 1/12 です。そして、支払い分が残高から引かれます。ローン初期残高(表示価格)を price、月々の支払額を monthlyPayment、ローン回数を loanTerm とするとき、年間利率(%) を求めなさい。(参考) ヒョウ本 P.257
●解答例３ (ローン利率を求める二分探索)
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
最後に整数の二分探索の関数も使ってみよう。
●問題例４
直線上に並ぶ、位置リストが A であるような N 個の小屋があります。M 頭の牛を、他の小屋とできるだけ離れるように入れるとき、最も近い２頭の間隔を最大化しなさい。(参考) アリ本 P.131
●解答例４ (整数での二分探索)
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() 関数を作る
- 関連記事
スポンサーサイト
tb: 0
cm: --
トラックバック
トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/195-9a4e2fb1
この記事にトラックバックする(FC2ブログユーザー)
| h o m e |
