技術系備忘録​/TypeScript​/二分探索(binary search) のソース :: シンクリッジ

• 差分^[1] を表示
• 技術系備忘録/TypeScript/二分探索(binary search)^[2] へ行く。

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

-配列内にお目当ての要素があるか否かだけの関数（いわゆる C++ で言う std::binary_search ）だけでなく、
最初に現れた指定値以上の要素の位置を返す関数（ std::lower_bound ）と、
最初に現れた指定値を超えた要素の位置を返す関数（ std::upper_bound ）を用意してます。
きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。

-単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。

-配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。
もちろん、正しくソートされてない配列の場合の結果は不定です。

** コード [#x0a2403a]
#prettify{{
// 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]);
}

}}

** サンプルコード [#lc2cf439]
#prettify{{
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}`);
}
}}

** サンプルコード の実行結果 [#k9dd6a18]
 -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


* よもやま [#h8e0186b]
- お気付きの方がおられたら嬉しいのですが、本稿は以前記載した [[技術系備忘録/PHP/二分探索(binary search)]] とほぼ同じです。なお、サンプルコード（テストケース）もまったく同じなのは手を抜いたとかではなく比較しやすいかなと考えた次第です。

- コードは TypeScript で記述してありますが、試しに動かしたいとか、素の JavaScript のコードが欲しいとかの場合は、[[こちらのサイト（TypeScript Playground）>https://www.typescriptlang.org/play/index.html]] にコピペしてみて下さい。とても便利で有難いサイトです。感謝です。

• 技術系備忘録/TypeScript/二分探索(binary search) のバックアップソース(No. All)
  • 現: 2020-06-03 (水) 10:09:06 takatsuka^[3]