汎用的に利用できる二分探索エンジンを作る

Posted at 2026-08-16

はじめに

この記事は下記の読者を対象とします。

二分探索の基本原理については既に理解している人。
二分探索の処理は簡単に書けるとはいえ，毎回似たような処理を書くのが面倒だと思っている人。
二分探索の処理は簡単に書けるので，いつも適当に書いて後でデバッグしている人。

二分探索の分類

二分法あるいは二分探索で解ける条件というのは，区間内で定義される評価関数が単調性を持つこと（単調増加あるいは単調減少であること）とされていますが，端的に言えば真偽値を返す評価関数に集約することができます。この評価関数は閉区間内で必ず true になる点を持つものとします。false から true へ，あるいは逆に true から false へ切り替わる点は最大で１つしかないものとします。最大で１つとは変化点がゼロの場合も許容し，全区間に渡って true の場合もあり得るものとしますが，逆に全区間に渡って false の場合はあり得ないとします。このとき評価関数の形状は以下の２ケースに分類できます。

実装コード

気の短い人もいるでしょうし，大して長くないコードなので実装コードをまず示します。ここでポイントは閉区間の境界 low と high に加えて，評価関数の形状 upstep，評価関数 evalfunc を引数として渡すように設計したことです。

二分探索関数

function	binsearch(low, high, upstep, evalfunc) {
	while(low < high) {
		if(upstep) {
			var	mid = (low + high) >> 1;
			if(evalfunc(mid))
				high = mid;
			else
				low = mid + 1;
		} else {
			var	mid = (low + high + 1) >> 1;
			if(evalfunc(mid))
				low = mid;
			else
				high = mid - 1;
		}
	}
	return low;
}

コード解説

(1) 中央値の計算方法

二分探索の中央値の計算方法について，下記の計算式のほうが正しいとされます。

var mid = low + ((high - low) >> 1);

これは mid = (low + high) >> 1 だと和を求めた時点でオーバーフローする場合を配慮してのこととされています。そんな巨大な数を JavaScript で取り扱わないのでそこまで配慮する必要はないと考えていますが，気になる人は書き換えて下さい。

ちなみに下記の例だと mid1 のみオーバーフローして負の値になりますが，mid2 と mid3 はオーバーフローしないで正しい値を得られます。※JScript9Legacy エンジンの場合

中央値の計算方法の比較

var	 low = 0x30000000;
var	high = 0x50000000;
var	mid1 = (low + high) >> 1;
var	mid2 = low + ((high - low) >> 1);
var	mid3 = Math.floor((low + high) / 2);

(2) 中央値の計算方法２

中央値の計算方法が upstep と downstep で違います。

upstepのとき

var mid = (low + high) >> 1;

downstepのとき

var mid = (low + high + 1) >> 1;

この差は終了直前の状態，すなわち high - low == 1 のときに顕著に現れます。中央値 mid は low あるいは high のいずれかを取ります。

中央値の計算方法	中央値
`mid = (low + high) >> 1`	`mid == low`
`mid = (low + high + 1) >> 1`	`mid == high`

評価関数の結果が true であろうと false であろうと，その次のステップで low >= high とならないと終了できません。図を見ると一目瞭然ですが，upstep のとき mid = high とすると評価関数が true のとき low も high も変化しないので終了できません。評価関数が false のときはループを脱出できますが，low != high となっていることに加えて low と high のいずれを選んでも正解とはなりません。mid の値を評価して false だったのだから正解は mid でないほうを選択しなくてはなりません。downstep のときは逆に mid = low とすると評価関数が false のとき終了できません。評価関数が true のときは辛うじてループを脱出できます。low != high となっていますが，low を選べば一応正解を得られます。

true のときの正解位置を○，false のときの正解位置を○で示します。

(3) 引数を減らしたい人へ

全区間に渡って評価関数が true の値を取り続けることはないのであれば，両端のデータを使って真偽値 upstep を自動判定することで引数を一つ減らせます。

upstep を自動判定する方法

function	binsearch(low, high, evalfunc) {
	var	upstep = !evalfunc(low) && evalfunc(high);
	/* 以下略 */
}

(4) 引数を減らしたい人へ２

３番目と４番目の引数の順番を入れ替えて，４番目の引数 upstep のデフォルト値を決めてしまうというのも良いでしょう。upstep の値が true で良いのなら指定を省略できます。

upstep のデフォルト値を true にする

function	binsearch(low, high, evalfunc, upstep = true) {
	/* 以下略 */
}

(5) 評価関数の引数を拡張

通常の用途では評価関数に引き渡すのは中央値 mid だけで十分ですが，評価関数の中で上限・下限を知りたい場合があります。その場合に備えて low と high を第２・３引数として与えても良いでしょう。

評価関数フルスペック版の呼び出し

if(evalfunc(mid, low, high))

もちろん評価関数を実装するとき，第２・３引数を使用しないのであれば省略可能です。

評価関数の中で上限・下限を知りたいケースについては別の記事にまとめようと思います。

使い方

upstep の実行サンプルを以下に示します。JavaScript なので評価関数をインラインで書けます。実行すると n = 5 を返します。先頭からサーチして 45 以上の最初の数 50 のインデクスです。

upstep の実行サンプル

var	a = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
var	n = binsearch(0, a.length - 1, true, function(x) {
	return a[x] >= 45;
});

downstep の実行サンプルです。実行すると n = 4 を返します。末尾からサーチして 45 以下の最初の数 40 のインデクスです。

downstep の実行サンプル

var	a = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
var	n = binsearch(0, a.length - 1, false, function(x) {
	return a[x] <= 45;
});

まとめ

二分探索自体はシンプルなアルゴリズムのため誰でも簡単に書けると思いますが，中央値の選定をよく考えないでコーディングすると正常終了できず無限ループに陥ったりします。またデータによっては終了できる場合がありますが，その場合も正解ではなく正解の隣の値を取得することがあります。このようなケアレスミスを失くすため，二分探索のエンジンを汎用部品化することを考えました。

評価関数をインラインで書けるので今回は JavaScript で実装しましたが，他言語への移植も容易でしょう。

参考文献

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up