メニュー
ブログ更新履歴
コンテンツ更新履歴
リンク
  • Magome
  • クラウドベースのMIDIシーケンサ
    音楽制作に興味のある方を対象に、スタンドアロンでも使え、ネットならではの面白さも兼ね備えた音楽制作アプリの提供を目指しています。
twitter

JavaScript には二分探索(バイナリサーチ)が標準で用意されてません。たぶん。
が、あれば便利だと思うので作ってみました。

  • 配列内にお目当ての要素があるか否かだけの関数(いわゆる C++ で言う std::binary_search )だけでなく、
    最初に現れた指定値以上の要素の位置を返す関数( std::lower_bound )と、
    最初に現れた指定値を超えた要素の位置を返す関数( std::upper_bound )を用意してます。
    きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。
  • 単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。
  • 配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。
    もちろん、正しくソートされてない配列の場合の結果は不定です。

コード anchor.png

// lower_bound
function lowerBound<T, U>(list: T[], value: U,
	less: (l: T, r: U) => boolean = (l: T, r: U) => l as any < r
): number {
	let count = list.length;
	let first = 0;
	while (0 < count) {
		const count2 = count / 2 | 0;
		const mid = first + count2;
		if (less(list[mid], value)) {
			first = mid + 1;
			count -= count2 + 1;
		} else {
			count = count2;
		}
	}
	return first;
}

// upper_bound
function upperBound<T, U>(list: T[], value: U,
	less: (l: U, r: T) => boolean = (l: U, r: T) => l as any < r
): number {
	return lowerBound(list,value,(l,r)=>!less(r,l));
}

// binary_search
// ・2つの比較関数というのがいささか冗長な気がしています。もう少しスマートな書き方がもしあれば教えてほしいです
function binarySearch<T, U>(list: T[], value: U,
	less0: (l: T, r: U) => boolean = (l: T, r: U) => l as any < r,
	less1: (l: U, r: T) => boolean = (l: U, r: T) => l as any < r
): boolean {
	const first = lowerBound(list, value, less0);
	return first >= list.length ? false : !less1(value, list[first]);
}
Page Top

サンプルコード anchor.png

const sortedList = [-5, 0, 5, 10, 10, 11, 11, 13, 18];      // ソート済みの配列
const testValues = [-7, -5, 0, 1, 2, 10, 12, 13, 18, 19];   // テストケース

for (const v of testValues) {
	const l = lowerBound(sortedList, v);
	const u = upperBound(sortedList, v);
	const b = binarySearch(sortedList, v);
	console.log(`${v} -> lowerBound=${l} : upperBound=${u} : binarySearch=${b}`);
}
Page Top

サンプルコード の実行結果 anchor.png

-7 -> lowerBound=0 : upperBound=0 : binarySearch=false
-5 -> lowerBound=0 : upperBound=1 : binarySearch=true
0 -> lowerBound=1 : upperBound=2 : binarySearch=true
1 -> lowerBound=2 : upperBound=2 : binarySearch=false
2 -> lowerBound=2 : upperBound=2 : binarySearch=false
10 -> lowerBound=3 : upperBound=5 : binarySearch=true
12 -> lowerBound=7 : upperBound=7 : binarySearch=false
13 -> lowerBound=7 : upperBound=8 : binarySearch=true
18 -> lowerBound=8 : upperBound=9 : binarySearch=true
19 -> lowerBound=9 : upperBound=9 : binarySearch=false
Page Top

よもやま anchor.png

  • お気付きの方がおられたら嬉しいのですが、本稿は以前記載した 技術系備忘録​/PHP​/二分探索(binary search) とほぼ同じです。なお、サンプルコード(テストケース)もまったく同じなのは手を抜いたとかではなく比較しやすいかなと考えた次第です。
  • コードは TypeScript で記述してありますが、試しに動かしたいとか、素の JavaScript のコードが欲しいとかの場合は、こちらのサイト(TypeScript Playground) にコピペしてみて下さい。とても便利で有難いサイトです。感謝です。

Front page   Freeze Diff Backup Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help   RSS of recent changes (RSS 1.0) RSS of recent changes (RSS 2.0) RSS of recent changes (RSS Atom) Powered by xpWiki
Counter: 501, today: 1, yesterday: 2
Princeps date: 2020-06-03 (Wed) 10:09:06
Last-modified: 2020-06-03 (Wed) 10:09:06 (JST) (178d) by takatsuka