ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »二分探索
このページの記事一覧

【C#】 LowerBound, UpperBound (二分探索)  


 私は時折、頭の体操代わりにプロコン問題を解いたりしているのだが、使う言語はその時々で変えてるので、関数によっては無いと不便に思うものがある。LowerBound, UpperBound はその代表例かな。ものによっては BinarySearch でも同じ結果を得られるものもあるが、やはりあった方が良いので改めて書いておくことにした。内容的には JavaRuby 版と同じ。使い所を覚えれば、簡潔かつ高速に処理できるので、二分探索系のアルゴリズムは知っておいても損はないだろう。




■C# 版 LowerBound, UpperBound

using System;
using System.Collections.Generic;

/// <summary>
/// 指定した値以上の先頭のインデクスを返す
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列(※ソート済みであること)</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値以上の先頭のインデクス</returns>
public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) < 0)
low = mid + 1;
else
high = mid;
}
return low;
}

//引数省略のオーバーロード
public static int LowerBound<T>(T[] arr, T value) where T : IComparable
{
return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

/// <summary>
/// 指定した値より大きい先頭のインデクスを返す
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列(※ソート済みであること)</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値より大きい先頭のインデクス</returns>
public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) <= 0)
low = mid + 1;
else
high = mid;
}
return low;
}

//引数省略のオーバーロード
public static int UpperBound<T>(T[] arr, T value)
{
return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

 ついでに引数省略のオーバーロードも書いてあるが、実際にはもう何パターンかあった方が便利かも知れない(全要素+IComparer指定 / 範囲指定+IComparer省略など)。もし予め検索の範囲が絞りこめるなら、更に高速に処理できるので範囲指定はオススメだ。プロコン問題やリアルタイム処理が必要な高負荷アプリケーションなどでは積極的に使っていこう。

 ちなみに返ってくるインデクスは LowerBound は「指定した値以上の先頭のインデクス」で、UpperBound は「指定した値より大きい先頭のインデクス」になる。BinarySearch の場合は、値が見つかった場合はそのインデクスが返り、見つからないとき負の値となり、ビット反転することで「指定した値より大きい先頭のインデクス」が返る(つまり毎回正負を調べる必要がある)。完全一致の有無を調べるには BinarySearch の方が便利だが、一番近い値のインデクス見つけるなら LowerBound や UpperBound の方が便利だ。使い分けると良いだろう。

 以降は簡単な使用例なので、既に知っているなら読み飛ばしても良いだろう。



■いくつかの値の範囲で何番目の要素かを求める

 例えば以下のような表があり、「ある風速に対して風力を求める」問題があったとする。実際にこの問題は AtCoder の練習問題の一部を抜粋したものだが、色々な人の解答例を見ていると(AtCoderyukicoder などは他の人の解答を見れるので勉強になる)、逐次検索または if 文で頭から値を比較しているものが圧倒的に多い。しかしこの表のように単調増加なものなら、二分検索が使えると考えて良い。この場合は UpperBound を使うと簡単だ。

風力風速
風力00.0m⁄s 以上 0.2m⁄s 以下
風力10.3m⁄s 以上 1.5m⁄s 以下
風力21.6m⁄s 以上 3.3m⁄s 以下
風力33.4m⁄s 以上 5.4m⁄s 以下
風力45.5m⁄s 以上 7.9m⁄s 以下
風力58.0m⁄s 以上 10.7m⁄s 以下
風力610.8m⁄s 以上 13.8m⁄s 以下
風力713.9m⁄s 以上 17.1m⁄s 以下
風力817.2m⁄s 以上 20.7m⁄s 以下
風力920.8m⁄s 以上 24.4m⁄s 以下
風力1024.5m⁄s 以上 28.4m⁄s 以下
風力1128.5m⁄s 以上 32.6m⁄s 以下
風力1232.7m⁄s 以上

●UpperBound を使っての解答例
//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = UpperBound(WindPower, ms) - 1;
Console.WriteLine("風速" + wp);

風速7

 実はこの問題の場合は BinarySearch でも事足りる。しかし BinarySearch の場合、値が見つかった時と見つからなかったときで処理を分岐する必要があり、冗長となることも多い。

●Array.BinarySearchを使っての解答例
//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = Array.BinarySearch(WindPower, ms);
Console.WriteLine("風速" + (wp < 0 ? ~wp - 1 : wp)); //見つからなかったときビット反転(~)するとUpperBoundと同じになる

風速7

 実際にはこの問題くらいの要素数なら逐次検索でも構わないのだが、要素数が何千とあったり、60fpsで動作するゲームなどでフレーム毎で使用する必要などあった場合、検索回数を大幅に減らせるので効果はてきめんとなる。



■検索する値の個数を求める

 次によくあるパターンだが、ある数が連続して並んでいるとき、その範囲や個数を調べる方法などもある。例えば以下のような表があったとき、「2~4 の値を持つインデクスの範囲とその要素数を求めたい」としよう。一番初めに思い浮かぶアルゴリズムは先頭から検索していき、2 が出てきた所で開始インデクスを記録、4 より上の値が出てきた所で終了インデクスを記録するといった感じだろうか。開始と終了の差を取ればその個数もわかる。しかし、ここでは LowerBound, UpperBound を使ってみよう。

Index[0][1][2][3][4][5][6][7][8][9][10][11][12]
Value0011122344455

//※・・・関数などは略・・・

int[] arr = {0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5}; //表
int low = 2; //検索する最小値
int high = 4; //検索する最大値
int from = LowerBound(arr, low); //検索する最小値で最初のインデクス
int to = UpperBound(arr, high); //検索する最大値を超えた最初のインデクス
Console.WriteLine("from = " + from + ", to = " + to + ", count = " + (to - from));

from = 5, to = 11, count = 6

 この例も要素数が少ない場合は逐次検索でもそれほど大差ないが、何千・何万という要素数でなら、圧倒的な速さとなる。



 私の見たところ、実際の開発現場でのコードでも逐次検索は多用されている感じがあるので、データが単調増加ないし単調減少なら二分探索を取り入れると良いと思う。確実に高速化できるし、もしデータを順に並べて良いものなら、予めリアルタイムにソート済みデータを作っていくアルゴリズムを組んでおけば、何かと便利なことが多い(Ruby 版だが「ソート済み配列を作る」方法もある[※C# なら List にすると良い])。

 この辺りは慣れだと思うが、常に検索回数を減らせるような工夫を忘れないようにすれば、paizaCodeIQ などの上級者問題(A, S ランク)も解けるようになる(タイムアウトしなくなる)。挑戦してみると良いだろう。


(関連記事)
【Ruby】二分探索, lower_bound, upper_bound
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


■参考になる書籍


スポンサーサイト

category: C#

thread: プログラミング

janre: コンピュータ

tag: C#ライブラリ  配列操作  二分探索 
tb: 0   cm: --

【Ruby】二分探索, lower_bound, upper_bound  


 Ruby2.3 以降には見つけた値のインデクスを返す Array.bsearch_index() があるのだが、自作した方が使い勝手が良いことも多いので、Java 版をそのまま移植してみた。


なお、組み込み関数の場合は以下のようになる。

●Ruby の bsearch_index で lower_bound, upper_bound 的な動作 (Ruby 2.3以降)
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;
lower = arr.bsearch_index{|x| x >= v} #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
upper = arr.bsearch_index{|x| x > v} #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
print "lower = #{lower}\n"
print "upper = #{upper}\n"

lower = 2
upper = 5

 値の意味は lower_bound 的な方は「指定した値以上の先頭の要素を返す」ことになるので、配列 arr 内で v = 3 が続く値の先頭インデクス = 2 を、upper_bound 的な方は「指定した値より大きい先頭の要素を返す」ことになるので、v = 3 が続く値より後ろのインデクス = 5 という意味になる。

 ちなみに Array.bsearch() の方は要素の値そのものを返す。今回の関数と組み込み関数との大きな違いは、値が見つからないとき nil (組み込み関数)か、近いインデクスを返す(今回の関数)かという感じだ。実は見つからないとき値を返すようにしておくと、色々利用できるのでわざわざ Java から(元はC++) 移植したわけだ。

●二分探索:binary_search, lower_bound, upper_bound (オープンクラス版)
#オープンクラス版
class Array
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(value, from = 0, to = self.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
elsif self[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end

end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値
print "binary_search = #{arr.binary_search(v)}\n"
print "lower_bound = #{arr.lower_bound(v)}\n"
print "upper_bound = #{arr.upper_bound(v)}\n"

print "bsearch_index(lower) = #{arr.bsearch_index{|x| x >= v}}\n" #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3)
print "bsearch_index(upper) = #{arr.bsearch_index{|x| x > v}}\n" #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3)

binary_search = 3
lower_bound = 2
upper_bound = 5
bsearch_index(lower) = 2
bsearch_index(upper) = 5

 意味は組み込み関数の例とだいたい同じになる。違いは値が見つからないときの戻値だ。例えば検索する値を v = 2 とすると、組み込み関数の場合 nil となるが、lower_bound()、upper_bound() は 2 となる。binary_search() の場合は -3 という値が返るが、この値はビット反転すると(~index = ~(-3))2 となる。つまり、binary_search() の場合、同値が連続しているとき、どのインデクスになるかは不定だが、負の値が返ってきたとき見つからなかったことがわかるので、処理分岐がしやすい利点がある。

 また、Ruby には関数のオーバーロードがないので、検索範囲を決める引数(from = 開始インデクス、to = 終了インデクス[このインデクスは含まない] はデフォルト値を設定してある(デフォは配列の最初から最後まで)。検索するインデクス範囲がわかっているなら、絞り込めば更に高速に動作する。余談だが、範囲を決める引数を関数に持たせる場合、終了インデクスは「含まない」としておくと、差分計算や連続検索などしやすくなる(標準ライブラリ等もだいたいそうなっている)。

 あと lower_bound() も upper_bound() も要素の最大より上の値を検索すれば、配列の長さと同じ値が返ってくる(例えば、v = 9 とすれば、どちらもインデクス = 15 が返る)。これらは値が見つからないとき、配列の最後に値を追加するのに使える。この方法を使えば、リアルタイムにソート済み配列を作ることも可能だ。試しにやってみよう。

●二分探索でソート済み配列を作る
arr = [3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
sorted = []

arr.each{|e|
sorted.insert(sorted.upper_bound(e), e)

# sorted.insert(sorted.lower_bound(e), e)

# idx = sorted.binary_search(e)
# if idx < 0
# idx = ~idx
# end
# sorted.insert(idx, e)
}

p arr
p sorted

[3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 この場合は binary_search(), lower_bound(), upper_bound() どれを使っても同じになる。しかし実際には同値がある場合、binary_search() は同値の中ではそのどこかに、lower_bound() の場合は同値の先頭に、upper_bound() の場合は同値の一番最後(=検索値の次の値の先頭)に挿入されることになる。追加順序が必要な場合は使い分けた方が良いだろう。もちろんこの例の場合は最後にソート(Array.sort())でも良いが、リアルタイムに追加・削除を繰り返す場合は、何度もソートするより負荷が軽くなる。

 もう1つ、lower_bound() と upper_bound() を上手く使う例として、指定範囲内の値の個数を求めてみよう。

●lower_bound() と upper_bound() で検索範囲内の値の個数を求める
arr = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]

lo, hi = 1, 3 #検索する値の範囲
fr = arr.lower_bound(lo) #開始インデクスを表す
to = arr.upper_bound(hi) #終了インデクスを表す[このインデクスは含まない]

p arr
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n" #差分が個数
p arr.slice(fr, to - fr) #範囲を抜き出し

[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]
fr = 3, to = 17, cnt = 14
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]

 この例は配列の中から、検索する値 = 1~3 のインデクス範囲(3~17 [17は含まない])を取得し、差分から個数を求めている。Array.slice() はおまけでその範囲を抜き出して表示しているだけだ。もちろんこのくらいの数なら逐次検索でもそれほど差がないかも知れないが、要素数が多くなると効果はてきめんとなる。

 最後にオープンクラスで使いたくない人のためにも通常のメソッドでも書いておこう。内容は全く同じになるので、好きな方を使えば良い。

●二分探索:binary_search, lower_bound, upper_bound (通常メソッド版)
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(arr, value, from = 0, to = arr.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
elsif arr[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値

print "binary_search = #{binary_search(arr, v)}\n"
print "lower_bound = #{lower_bound(arr, v)}\n"
print "upper_bound = #{upper_bound(arr, v)}\n"

s, e = 3, 6 #検索する値の範囲
fr = lower_bound(arr, s)
to = upper_bound(arr, e)
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"

binary_search = 3
lower_bound = 2
upper_bound = 5
fr = 2, to = 12, cnt = 10


 オンラインジャッジの問題でも上級レベルになるほど、逐次検索では計算量が間に合わずタイムアウトしやすくなる。CodeIQ でも paiza でもランク A, S(★★★★)問題には必要となるシーンも多いので、使える場合は積極的に使ってみると良いだろう(要するに単純な昇順・降順データ・累積和・フィボナッチのような増加数列には使った方が安全)。標準ライブラリにあるものでも、その実装に近いものを知っていれば柔軟に対応できるようになるので、色々改造して使うと良いだろう。


(関連記事)
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


■参考になる書籍


category: Ruby

thread: プログラミング

janre: コンピュータ

tag: 配列操作  二分探索 
tb: 0   cm: --

【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: --

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


 「プログラミングコンテストチャレンジブック [第2版]」(通称:アリ本)を見ていて、ちょっと気になる解法があったのだが、C++ のライブラリの「lower_bound()」を使っていたので Java では試せなかった。というわけで Java に lower_bound(), upper_bound() を移植してみた。ちなみにこの2つの関数は二分探索の関数で、lower_bound() は「指定した値以上の先頭の要素を返す」関数で、upper_bound() は「指定した値より大きい先頭の要素を返す」関数だ。Java 標準ライブラリの「Arrays.binarySearch()」も二分探索のライブラリだが、同じ値が並んでいるときは、返ってくる要素は不定になり、見つからなかった場合は負の値になる。これら関数は、基本的に見つかった値に対して、返ってくる要素(インデクス)が違うだけと考えて良い。今回は配列内の要素での探索に使う。

●Java 版 lower_bound(), upper_bound()
/**<h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が0のときは、0が返る。</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>配列要素が0のときは、0が返る。</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;
}

 気になった解法というのは、「アリ本 [第2版]」の P.135 ページにある「Subsequence」(部分列問題)のはじめの方の解法だ。問題としては、

長さ N の数列 A と、整数 S が与えられます。A の連続する部分列で、その総和が S 以上となるようなもののうち、最小の長さを求めなさい。

というものだが、「最初から各インデクスまでの部分和を配列に記録し、各インデクスからの部分和で S 以上となる、先頭のインデクスを二分探索する」というアルゴリズムで解いている。これは要素がすべて正の数なら、その部分和は単調増加になるので、二分探索が適用できるというものだ。上の「lowerBound()」を使って、Java で書いてみよう。

●Java 版 二分探索を使った Subsequence 解法
//メインコード
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);
}

2

 といっても、この問題はその後にある「しゃくとり法」の方が、より効率が良いんだけどね。ただ、配列の中身がバラバラの数値(単調増加でない数列)だったので、部分和の二分探索は思い付かなかった。単純な全探索でも解けるけど、要素数が多いと計算量が間に合わないからね。解法は色々知っていて損はない。まぁ、ライブラリがないとこの解法はすぐにはできないが…。


 また、これら2つの関数を組み合わせると、「同じ値の連続した区間」を高速に求めることができる。例えば以下のように配列にデータが入っていたとして、探す値を v としたとき、2つの関数の差分を取れば良い。

●「同じ値の連続した区間」を二分探索で求める
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);

3

 これは 3 の値が「連続で 3 個」あることを表している。


 ちなみにもう一つ工夫して、引数に Comparator を使ったりすると、単調減少でも利用することができる。ただし返る値は「見つかった値より後ろのインデクス」のようになるけどね。ほんの少し改造版も載せておこう。

●Comparator を追加した、単調減少で探索できる lower_bound(), upper_bound()
/**<h1>指定した値と同じか後ろにある、先頭のインデクスを返す</h1>
* <p>配列要素が0のときは、0が返る。</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>配列要素が0のときは、0が返る。</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; //降順
}
});


 あとは、探索対象の開始と終了インデクスも引数に追加して、配列の一部のみの探索も可能にするといいね。この記事でのコードは1つ1つの関数で書いてしまっているけど、一番多く引数を持つ関数を1つだけ作って、あとは引数を変えた関数をオーバーロードをしてしまう方が楽だ。必要ならば自分で作ってみると良いだろう。


(関連記事)
【Java】二分探索を汎用的に使えるようにする
【Ruby】二分探索, lower_bound, upper_bound
【Java】配列要素の反転(reverse)
【Java】2次元配列のソート
【Java】連想配列(Map)を値でソートする


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: 二分探索  配列操作  アルゴリズム  練習問題 
tb: 0   cm: --
IS<インフィニット・ストラトス> アーキタイプ・ブレイカー
キルドヤ


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop