JavaScriptの二分探索（バイナリサーチ）でソート済み配列を検索する方法

問題

昇順にソートされた数値の配列 arr を第1引数に、検索したい数値 target を第2引数として受け取るJavaScript関数を作成します。配列がすでにソートされているため、二分探索（バイナリサーチ）アルゴリズムを使って target を効率的に検索します。

target が配列内に存在する場合はそのインデックスを返し、存在しない場合は -1 を返す必要があります。

入出力の例

たとえば、関数への入力が次の場合を考えます。

入力

const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28];
const target = 13;

出力

const output = 5;

コード例

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

const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28];
const target = 13;

const binarySearch = (arr = [], target) => {
  const helper = (low, high) => {
    if (low > high) {
      return -1;
    }
    const middle = Math.floor((low + high) / 2);
    if (arr[middle] === target) {
      return middle;
    }
    if (arr[middle] < target) {
      return helper(middle + 1, high);
    }
    return helper(low, middle - 1);
  };
  return helper(0, arr.length - 1);
};

console.log(binarySearch(arr, target));

出力

5

二分探索の仕組み

このコードの動作を簡単に解説します。

• 中央要素との比較: まず探索範囲 [low, high] の中央インデックス middle を求め、その要素 arr[middle] を target と比較します。
• 一致した場合: arr[middle] === target であれば、そのインデックス middle を即座に返します。
• target が大きい場合: arr[middle] < target なら、target は配列の右半分にあるため、探索範囲を [middle + 1, high] に絞り込みます。
• target が小さい場合: 逆に arr[middle] > target なら、左半分 [low, middle - 1] に絞って再度探索します。
• 見つからない場合: low が high を超えると探索範囲が空になったことを意味するため、-1 を返します。

各ステップで探索範囲が半分になるため、計算量は O(log n) と非常に効率的です。たとえば100万件のデータでも、最大20回程度の比較で目的の値を見つけることができます。線形探索の O(n) と比べると、大規模なソート済みデータの検索において圧倒的なパフォーマンスを発揮します。