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

コード ^[1]

// 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]);
}

サンプルコード ^[2]

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}`);
}

サンプルコード の実行結果 ^[3]

-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

よもやま ^[4]

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

• コードは TypeScript で記述してありますが、試しに動かしたいとか、素の JavaScript のコードが欲しいとかの場合は、こちらのサイト（TypeScript Playground）^[6] にコピペしてみて下さい。とても便利で有難いサイトです。感謝です。