JavaScriptでターゲット文字より大きい最小の文字を二分探索で見つける方法

問題の概要

小文字の英字のみを含むソート済みの文字配列 letters と、ターゲットとなる文字 target が与えられます。

求められているのは、配列を第一引数、文字を第二引数として受け取り、「ターゲットより大きい文字の中で最小のもの」を配列から見つけ出すJavaScript関数を作成することです。

注意すべきポイントとして、文字は周回(ラップアラウンド)するという仕様があります。たとえば target = 'z'、letters = ['a', 'b'] の場合、ターゲットより大きい文字は存在しないため、先頭に戻って答えは 'a' となります。

入出力例

たとえば、入力となる配列と文字が次の場合を考えてみましょう。

const arr = ["c", "f", "j"];
const target = "a";

このとき、期待される出力は次の通りです。

const output = "c";

解決策:二分探索による実装

配列がすでにソートされているため、先頭から順に調べる線形探索ではなく、二分探索(バイナリサーチ)を活用すれば、O(log n) の計算量で効率的に答えを求められます。

アルゴリズムの流れは以下の通りです。

• 探索範囲の中央にある要素がターゲット以下であれば、答えは右側にあるため、探索範囲を右側に狭める
• 中央の要素がターゲットより大きければ、その位置が答えの候補になるため、探索範囲を左側に狭める
• ループ終了時の左端のインデックスが答えの位置。ただし、その位置が配列の末尾を超えている場合は、ラップアラウンドの仕様に従い先頭の文字を返す

サンプルコード

const arr = ["c", "f", "j"];
const target = "a";

const findSmallestLetter = (letters = [], target = '') => {
  let left = 0;
  let right = letters.length - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (letters[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // ラップアラウンド処理:該当する文字がない場合は先頭の文字を返す
  if (left === letters.length) {
    return letters[0];
  }
  return letters[left];
};

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

実行結果

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

c

まとめ

ソート済みの配列が前提となるこの種の問題では、二分探索を使うことで要素数が多い場合でも高速に処理できます。また、探索結果が配列の範囲外になったケースを「先頭への周回」として扱うことで、ラップアラウンドの仕様にも正しく対応できます。同様のパターンは、ソート済みデータから特定の条件を満たす最小値・挿入位置を求める場面で広く応用できるので、ぜひ覚えておきましょう。