JavaScript
アルゴリズム

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

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

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

1. 重複を許す二分挿入

今回は簡単のため、配列に直接メソッドを追加していますが、本当は別クラスにしたりした方が良さそうです。
(Array.prototype をいじるのはよくないみたい。)

var array = [2, 4, 6, 8];

array.insert = function(value) {

    var lower = 0;
    var upper = this.length;

    while ( lower < upper ) {

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

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

    }

    this.splice(lower, 0, value);

};

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

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

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

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

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

上記のコードはほとんど以下のサイトの移植版ですが、array[lower] == valueのチェックを無くしているのが今回のミソです。

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

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

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

var array = [2, 4, 6, 8];

array.insert = function(value) {

    var lower = 0;
    var upper = this.length;

    while ( lower < upper ) {

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

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

    }

    // 重複しない場合
    if ( this[lower] != value ) {
        this.splice(lower, 0, value);
    }

};

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

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

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

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

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

オブジェクトの特定のプロパティに関して並び替えたい場合、値が一致したときはオブジェクトを上書きしたい、みたいなこともできます。

var array = [
    {id: 2, name: 'い'},
    {id: 4, name: 'え'}
];

array.insert = function(value) {

    var lower = 0;
    var upper = this.length;

    while ( lower < upper ) {

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

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

    }

    // 上書き・挿入
    if ( lower in this && this[lower].id == value.id ) {
        this[lower] = value;
    } else {
        this.splice(lower, 0, value);
    }

};

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

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

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

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

4. 二分挿入ソート

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

var arrayOld = [5, 2, 7, 4, 9];
var arrayNew = [];
while ( arrayOld.length != 0 ) {
    arrayNew.insert(arrayOld.shift());
}

(insert() の定義は省略しましたが、使うなら「1. 重複を許す二分挿入」のが良いと思います。)

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

(upper + lower) / 2 でも大体は同じ結果になりますが、upperlower がコードで扱えるギリギリ大きい整数だと (upper + lower) で問題が起きます。
lower + (upper - lower) / 2 ならギリギリ大きくても行けます。

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

(とはいえ、どちらにせよ、扱えない大きさの数値は絶対あるし、やっぱり (upper + lower) / 2 でも良いような気もします…。)

6. lower == upper について

今回参考にしたコードでは、値が見つかったかのチェックに lower == upper という条件式を含んでいるのですが、配列が空の場合も含め常に true になる気がします…。