JavaScript で Array に二分探索して挿入する

ありそうでなかったので書きます。

単にソートするなら Array.prototype.sort() を使えば良いですが、(イベントなどで) 後から要素を配列に追加していく場合、ソートでなくその場で挿入するのが良いと思い、二分探索して挿入してみました。

1. 二分挿入

1.1. 重複を許す二分挿入

const insert = (array, value) => {

    let lower = 0;
    let upper = array.length;

    while ( lower < upper ) {

        // 以下のコードだと扱える範囲が狭まる
        // (upper + lower) / 2
        const mid = Math.floor(lower + (upper - lower) / 2);

        if ( array[mid] < value ) {
            lower = mid + 1;
        } else {
            upper = mid;
        }

    }

    array.splice(lower, 0, value);

};

// 
// テスト
// 
const array = [2, 4, 6, 8];

insert(array, 0);
console.log(array); // [0, 2, 4, 6, 8]

insert(array, 10);
console.log(array); // [0, 2, 4, 6, 8, 10]

insert(array, 5);
console.log(array); // [0, 2, 4, 5, 6, 8, 10]

insert(array, 8);
console.log(array); // [0, 2, 4, 5, 6, 8, 8, 10]

挿入する目的では一致する値を見つける必要はないので、「value 以上のインデックスが最も小さい要素」を見つけ、そこに要素を挿入しています。

上記のコードはほぼ以下のサイトのコードの移植ですが、array[lower] == value のチェックを無くしたのが今回のポイントです。

参考「値が重複している場合 - 二分探索 | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第４章」

1.2. 重複を許さない二分挿入

重複を許さない場合もできます。
(重複チェックを追加)

const insert = (array, value) => {
	
	let lower = 0;
	let upper = array.length;
	
	while ( lower < upper ) {
		
		// 以下のコードだと扱える範囲が狭まる
		// (upper + lower) / 2
		const mid = Math.floor(lower + (upper - lower) / 2);
		
		if ( array[mid] < value ) {
			lower = mid + 1;
		} else {
			upper = mid;
		}
		
	}
	
	// 重複しない場合
	if ( array[lower] != value ) {
		array.splice(lower, 0, value);
	}
	
};

// 
// テスト
// 
const array = [2, 4, 6, 8];

insert(array, 0);
console.log(array); // [0, 2, 4, 6, 8]

insert(array, 10);
console.log(array); // [0, 2, 4, 6, 8, 10]

insert(array, 5);
console.log(array); // [0, 2, 4, 5, 6, 8, 10]

insert(array, 8);
console.log(array); // [0, 2, 4, 5, 6, 8, 10]

1.3. 重複を上書きする二分挿入

オブジェクトの配列に挿入したいとき、あるプロパティの値が一致したときにを新しいオブジェクトに置き換える、というような二分挿入です。

const insert = (array, value) => {
	
	let lower = 0;
	let upper = array.length;
	
	while ( lower < upper ) {
		
		// 以下のコードだと扱える範囲が狭まる
		// (upper + lower) / 2
		const mid = Math.floor(lower + (upper - lower) / 2);
		
		if ( array[mid].id < value.id ) {
			lower = mid + 1;
		} else {
			upper = mid;
		}
		
	}
	
	// 上書き・挿入
	if ( lower in array && array[lower].id == value.id ) {
		array[lower] = value;
	} else {
		array.splice(lower, 0, value);
	}
	
};

const getNames = array => array.reduce((str, obj) => str + obj.name, '');

// 
// テスト
// 
const array = [
	{id: 2, name: 'い'},
	{id: 4, name: 'え'}
];

insert(array, {id: 1, name: 'あ'});
console.log(getNames(array)); // あいえ

insert(array, {id: 3, name: 'う'});
console.log(getNames(array)); // あいうえ

insert(array, {id: 5, name: 'お'});
console.log(getNames(array)); // あいうえお

insert(array, {id: 2, name: 'き'});
console.log(getNames(array)); // あきうえお

2. おまけ

2.1. 二分挿入ソート

今回のコードを流用して二分挿入ソートもできます。

const arrayOld = [5, 2, 7, 4, 9];
const arrayNew = [];

while ( arrayOld.length != 0 ) {
	insert(arrayNew, arrayOld.shift());
}

console.log(arrayNew); // [2, 4, 5, 7, 9]

insert() の定義は「1.1. 重複を許す二分挿入」を使います。

2.2. lower + (upper - lower) / 2 について

(upper + lower) / 2 でも同じに見えますが、扱える数値の範囲が異なります。
upper と lower がかなり大きい整数だと (upper + lower) が正しく計算できません。
lower + (upper - lower) / 2 なら upper と lower が大きくてもその差があまり大きくなければ計算できます。

参考「二分探索 - Wikipedia」
参考「数値 | JavaScript プログラミング解説」

(あまり大きい配列を扱わないなら (upper + lower) / 2 でも良いと思います…)

2.3. 空配列の対処について

今回参考にしたリンク先のコードでは、条件式 lower == upper で配列が空ではないかどうかを確認しようとしているのですが、空の場合も常に true になる気がします…。