モダンJavaScript入門: 二分探索法を用いて配列内の要素を検索する方法

1. 二分探索法とは

二分探索法は、ソート済みのリストや配列に対して高速な検索を行うためのアルゴリズムです。この方法では、中央の要素を見て、検索対象が中央の要素よりも大きいか小さいかを確認し、それに応じて探索範囲を半分に絞り込むという操作を繰り返します。

2. 二分探索法のアルゴリズム

以下に二分探索法の基本的なアルゴリズムを示します。 1. 配列の中央の要素を見る。 2. 中央の要素が検索対象と一致していれば、そのインデックスを返す。 3. 検索対象が中央の要素よりも大きければ、中央よりも右側の部分配列で探索を続ける。 4. 検索対象が中央の要素よりも小さければ、中央よりも左側の部分配列で探索を続ける。

3. JavaScriptでの二分探索法の実装

以下に、JavaScriptを用いて二分探索法を実装した例を示します。

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (array[mid] === target) {
      // 目的の値が見つかった場合
      return mid;
    } else if (array[mid] < target) {
      // 目的の値が中央値より大きい場合
      left = mid + 1;
    } else {
      // 目的の値が中央値より小さい場合
      right = mid - 1;
    }
  }

  return -1; // 目的の値が見つからなかった場合
}

4. 二分探索法の応用例

二分探索法は、大きなデータセットに対する検索を高速化するための手法としてよく用いられます。以下に、その応用例を3つ示します。

例1: 配列内の特定の値を見つける

二分探索法は、配列内の特定の値を見つけるために利用できます。以下にその例を示します。

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let target = 7;

let index = binarySearch(array, target); // 6

例2: 固定長の配列から範囲内の値を見つける

固定長の配列から特定の範囲内の値を見つけるためにも二分探索法を利用できます。

let array = [10, 20, 30, 40, 50];
let target1 = 25;
let target2 = 45;

let index1 = binarySearch(array, target1); // -1 (見つからない)
let index2 = binarySearch(array, target2); // 3

例3: ソート済みの文字列配列から特定の文字列を検索する

ソート済みの文字列配列から特定の文字列を検索するためにも二分探索法を利用できます。

let array = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
let target = 'cherry';

let index = binarySearch(array, target); // 2

以上、二分探索法を用いて配列内の要素を検索する方法について解説しました。このアルゴリズムを理解し、自身のコードに適切に応用することで、大きなデータセットに対する検索性能を大幅に向上させることができます。

AIko Code Symphony