JavaScriptでのバイナリサーチの実装方法

まず、以下にシンプルなバイナリサーチの実装例を示します。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid; // 要素が見つかった場合、インデックスを返す
    } else if (arr[mid] < target) {
      left = mid + 1; // 中央よりも大きい場合、右半分を探索
    } else {
      right = mid - 1; // 中央よりも小さい場合、左半分を探索
    }
  }
  return -1; // 要素が見つからなかった場合、-1を返す
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 6;
const result = binarySearch(arr, target);
console.log("要素が見つかった位置: " + result);

上記のコードでは、binarySearch関数がソート済みの配列と目標の要素を受け取り、バイナリサーチを実行します。アルゴリズムの基本的なアイデアは、配列を常に中央で分割し、目標の要素を見つけるまで探索範囲を絞り込むことです。

この実装では、leftとright変数を使用して探索範囲の開始と終了インデックスを追跡します。whileループの中で、中央のインデックスを計算し、中央の要素と目標の要素を比較します。目標の要素が見つかった場合は、そのインデックスを返します。目標の要素が中央の要素よりも大きい場合は、右半分を探索するためにleftを更新します。目標の要素が中央の要素よりも小さい場合は、左半分を探索するためにrightを更新します。

もし要素が見つからなかった場合は、-1を返します。

このコード例を使って、任意のソート済み配列でバイナリサーチを実行することができます。バイナリサーチは、要素数が多いリストや配列で特に効果的です。