JavaScriptでソート済みの2次元配列を二分探索アルゴリズムで検索する方法

この記事では、数値の配列の配列（2次元配列）を第1引数に、検索対象の数値を第2引数として受け取るJavaScript関数を作成します。

各サブ配列（内側の配列）には昇順にソートされた数値が格納されており、さらに前のサブ配列のどの要素も、後続のサブ配列のどの要素よりも大きくならないものとします。つまり、2次元配列全体が行ごとにも全体としても昇順に並んでいる状態です。

この関数は二分探索（バイナリサーチ）アルゴリズムを使用し、ソートされた配列の中から指定された要素を効率的に検索します。要素が存在する場合は true を、存在しない場合は false を返します。

入力例

たとえば、入力配列が次の場合を考えます。

const arr = [
    [2, 6, 9, 11],
    [13, 16, 18, 19, 21],
    [24, 26, 28, 31]
];
const num = 21;

この場合、21 は2番目のサブ配列内に存在するため、出力は次のようになります。

const output = true;

実装コード

以下が実際のコードです。

const arr = [
    [2, 6, 9, 11],
    [13, 16, 18, 19, 21],
    [24, 26, 28, 31]
];
const num = 21;
const search2D = (array = [], target) => {
    const h = array.length;
    const w = h > 0 ? array[0].length : 0;
    if (h === 0 || w === 0) { return false; }
    const arr = getArr();
    if (!arr) { return false; }
        return binarySearch(arr, target) !== null;
    function getArr() {
        for (let i = 0; i < h; i++) {
            let arr = array[i];
            if (arr[0] <= target && target <= arr[arr.length - 1]) {
                return arr;
            }
        }
        return null;
    }
    function binarySearch(arr, t) {
        let left = 0;
        let right = arr.length - 1;
        while (left <= right) {
            if (arr[left] === t) {
                return left;
            }
            if (arr[right] === t) {
                return right;
            }
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] === t) {
                return mid;
            }
            if (arr[mid] < t) {
                left = mid + 1;
            }
            else if (arr[mid] > t) {
                right = mid - 1;
            }
        }
        return null;
    }
};
console.log(search2D(arr, num))

コードの解説

この実装は、大きく分けて次の手順で動作します。

1. 前提条件のチェック： 配列の高さ（h）と幅（w）を取得し、空の配列が渡された場合は即座に false を返します。

2. 対象行の特定（getArr）： 各サブ配列について、その行の先頭要素と末尾要素の間にターゲット値が収まっているかどうかを判定します。ターゲットが範囲内にある行だけが候補となり、それ以外の行は早期に除外できるため、無駄な探索を省けます。

3. 二分探索の実行（binarySearch）： 見つかった行に対して、左右両端の要素をまず確認し、次に中央の要素との大小比較を繰り返しながら探索範囲を半分ずつ狭めていきます。これにより、線形探索と比べて大幅に少ない比較回数で目的の要素を見つけられます。

要素が見つかればインデックスが返され、最終的に true となります。見つからなければ null が返され、false となります。

出力結果

コンソールには次のように表示されます。

true