二分探索のライブラリ化

// Competitive Programming (2) Advent Calendar 2019 の 20 日目の記事です。

競技プログラミングでたびたび利用する二分探索について考察してみます。
といっても、とくに競技プログラミングに限らず活用できると思います。言語は C# です。

まず二分探索の基本的な例として、昇順にソートされた整数のリスト a に対して「値 v をリストに挿入するときのインデックス」を求めてみます。 これは「値 v より大きい値が最初に現れるインデックス」と考え、最後の要素が v 以下のときはリストの長さ a.Count を返すことにすれば、次の IndexForInsert メソッドとして実装できます。

	using System;
	using System.Collections.Generic;
	namespace AlgorithmLib
	{
	public static class SearchSample0
	{
	// 指定された値よりも大きい値を持つ最初のインデックスを求めます。
	// これは、挿入先のインデックスを意味します。
	public static int IndexForInsert(IList<int> a, int v)
	{
	int l = 0, r = a.Count, m;
	while (l < r)
	{
	m = l + (r - l - 1) / 2;
	if (a[m] > v) r = m;
	else l = m + 1;
	}
	return r;
	}
	// 指定された値以上の値を持つ最初のインデックスを求めます。
	// Array.BinarySearch メソッドと同様に、一致する値が存在しない場合はその補数を返します。
	// ただし Array.BinarySearch メソッドでは、一致する値が複数存在する場合にその最初のインデックスを返すとは限りません。
	public static int IndexOf(IList<int> a, int v)
	{
	int l = 0, r = a.Count, m;
	while (l < r)
	{
	m = l + (r - l - 1) / 2;
	if (a[m] >= v) r = m;
	else l = m + 1;
	}
	return r < a.Count && a[r] == v ? r : ~r;
	}
	}
	}

view raw SearchSample0.cs hosted with ❤ by GitHub

同じ考え方を利用して、Array.BinarySearch メソッドのように「値が一致するインデックスを求める。一致しない場合は、それより大きな値のインデックスの補数」という仕様にするには、上の IndexOf メソッドのように書けます。

注意点:

• IList<T> インターフェイスは、 T[] や List<T> クラスを含みます。
• リスト内の値は重複してもかまいません。
• 例外処理は除いています。
• (l + r - 1) / 2 とするとオーバーフローすることがあるため、 l + (r - l - 1) / 2 としています。

上記のメソッドは、リストのみ、しかも昇順にソート済みという制約の下で適用することができます。
そこで、さらに汎用的に使えるように、抽象度を上げてライブラリを作ることを考えます。

二分探索により実現できることは、見方を変えると「状態が変化する境界を見つけること」、厳密には「与えられた条件に対し、ある境界が存在して、その前方と後方で真偽が逆転する場合にその境界を見つけること」だと考えます。
この考え方で先ほどのコードから抽象化した部分を抜き出すと、次の First メソッドのようになります。

	using System;
	namespace AlgorithmLib
	{
	/// <summary>
	/// 二分探索のためのメソッドを提供します。
	/// </summary>
	public static class BinarySearch
	{
	/// <summary>
	/// 条件 f を満たす最初の値を探索します。
	/// [l, x) 上で false、[x, r) 上で true となる x を返します。
	/// f(l) が true のとき、l を返します。
	/// f(r - 1) が false のとき、r を返します。
	/// </summary>
	/// <param name="f">半開区間 [l, r) 上で定義される条件。</param>
	/// <param name="l">探索範囲の下限。</param>
	/// <param name="r">探索範囲の上限。</param>
	/// <returns>条件 f を満たす最初の値。</returns>
	public static int First(Func<int, bool> f, int l, int r)
	{
	int m;
	while (l < r)
	if (f(m = l + (r - l - 1) / 2)) r = m;
	else l = m + 1;
	return r;
	}
	}
	}

view raw BinarySearch.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	namespace AlgorithmLib
	{
	public static class SearchSample1
	{
	// 指定された値よりも大きい値を持つ最初のインデックスを求めます。
	// これは、挿入先のインデックスを意味します。
	public static int IndexForInsert(IList<int> a, int v) =>
	BinarySearch.First(i => a[i] > v, 0, a.Count);
	// Array.BinarySearch メソッドと異なる点: 一致する値が複数存在する場合は最初のインデックス。
	public static int IndexOf(IList<int> a, int v)
	{
	var r = BinarySearch.First(i => a[i] >= v, 0, a.Count);
	return r < a.Count && a[r] == v ? r : ~r;
	}
	}
	}

view raw SearchSample1.cs hosted with ❤ by GitHub

この形にすれば、降順のリストにも、リスト以外の数値の範囲にも適用できます。
例として、AtCoder の ABC 146 C – Buy an Integer を解いてみます。
先ほどの First メソッドに対して Last メソッドを用意し (コメントは省略)、価格が所持金以下となる最後の整数を求めればよいです。

	using System;
	class C
	{
	static void Main()
	{
	var h = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
	Console.WriteLine(Last(n => h[0] * n + h[1] * n.ToString().Length <= h[2], 0, 1000000000));
	}
	// 条件 f を満たす最後の値を探索します。
	static int Last(Func<int, bool> f, int l, int r)
	{
	int m;
	while (l < r) if (f(m = r - (r - l - 1) / 2)) l = m; else r = m - 1;
	return l;
	}
	}

view raw C.cs hosted with ❤ by GitHub

だいぶ簡潔に書けました。

次に小数向けのメソッドを用意して、二分法で平方根を求めてみます。
誤差を表す桁数を指定できるようにしています。

	using System;
	namespace AlgorithmLib
	{
	/// <summary>
	/// 二分探索のためのメソッドを提供します。
	/// </summary>
	public static class BinarySearch
	{
	/// <summary>
	/// 条件 f を満たす最初の値を指定された誤差の範囲内で探索します。
	/// (l, x) 上で false、[x, r) 上で true となる x を返します。
	/// l 近傍で true のとき、l を返します。
	/// r 近傍で false のとき、r を返します。
	/// </summary>
	/// <param name="f">開区間 (l, r) 上で定義される条件。</param>
	/// <param name="l">探索範囲の下限。</param>
	/// <param name="r">探索範囲の上限。</param>
	/// <param name="digits">誤差を表す小数部の桁数。</param>
	/// <returns>条件 f を満たす最初の値。</returns>
	public static double First(Func<double, bool> f, double l, double r, int digits = 9)
	{
	double m;
	while (Math.Round(r - l, digits) > 0)
	if (f(m = l + (r - l) / 2)) r = m;
	else l = m;
	return r;
	}
	}
	}

view raw BinarySearch.cs hosted with ❤ by GitHub

	using System;
	namespace AlgorithmLib
	{
	public static class SearchSample1
	{
	public static double Sqrt(double v, int digits = 9) =>
	BinarySearch.First(x => x * x >= v, Math.Min(1, v), Math.Max(1, v), digits);
	}
	}

view raw SearchSample1.cs hosted with ❤ by GitHub

まとめ

というわけで、今後は二分探索の問題を意味論的に「与えられた条件を満たす最初または最後の値を求める」と考えれば、
今回作成したライブラリを使って実装ができます。

• 作成したライブラリとサンプル コード (GitHub)

その他

• これまでは二分探索を実装するときに再帰を使っていたのですが、おそらく過去に読んだ解説に再帰を使うものが多かったためだと思います。競技プログラミングを始めてから自然に while (l < r) を使うようになりました。
• Array.BinarySearch メソッドや List.BinarySearch メソッドでは、重複する値を検索する場合、その最初のインデックスが返ってくるとは限りません。

前回: 競技プログラミングでも C# で簡潔に書きたい
次回: 数論・素数に関するメソッドを実装する

参照

• 二分探索 – Wikipedia
• 本当に不足しているIT人材を知るために、本当に必要なもの | ウェブ電通報