🔍

TypeScriptでBinary Search(二分探索)を実装してみる

2023/02/05に公開

JavaScript

TypeScript

algorithm

tech

どうもoreoです。

今回はTypeScriptでBinary Searchを実装してみます。

Binary Searchとは？

データが予めソートされている場合に、探索範囲を半分に絞ることを繰り返して、データ探索する手法です。

電話帳で連絡先を探すときに真ん中のページを開くことを繰り返して連絡先を探す、みたいな例でよく聞くアルゴリズムです。

計算量は、O(log n)でデータ量が増えても計算時間はあまり増えません。

TypeScriptでの実装

事前に昇順にソートされた配列arrと、探索したい値targetを渡すと、Binary Searchしてくれる関数binarySearchを作成します。

targetがarrに存在する場合、arrで最初にtargetが出現するindexを返し、存在しない場合は-1を返します。

/**
 * @param {Array<number>} arr 事前に昇順にソートされた配列
 * @param {number} target arrに存在するか探索したい値
 * @return {number}
 */

function binarySearch(arr: number[], target: number): number {
  // 探索配列の左端と右端のindex
  let left = 0,
    right = arr.length - 1;

  while (left <= right) {
    // 探索配列の中間のindex
    const mid = Math.floor((left + right) / 2);

    if (target < arr[mid]) {
      // 探索配列の中間の要素よりtargetが小さい場合、探索配列の右端を変更する。
      // 次回の繰り返し処理では今回の探索配列の左半分を探索する
      right = mid - 1;
    } else if (target > arr[mid]) {
      // 探索配列の中間の要素よりtargetが大きい場合、探索配列の左端を変更する。
      // 次回の繰り返し処理では今回の探索配列の右半分を探索する
      left = mid + 1;
    } else {
      //探索配列の中間の要素がtargetと等しい場合、それを返す。
      return mid;
    }
  }

  // targetがarrの中にない場合は、-1を返す
  return -1;
}

console.log(binarySearch([1, 5, 6, 10], 5)); // 1
console.log(binarySearch([1, 5, 6, 6, 6, 10], 6)); // 2
console.log(binarySearch([-1, 0, 2, 5, 6, 8, 9, 10], 0)); //1

再起的に処理させる場合は以下のようにも書けます。


/**
 * @param {Array<number>} arr 事前に昇順にソートされた配列
 * @param {number} target arrに存在するか探索したい値
 * @return {number}
 */

function binarySearch(arr: number[], target: number): number {
  // 探索配列の左端と右端のindex
  let left = 0,
    right = arr.length - 1;
  return binarySearchImpl(arr, target, left, right);
}

//再起的に処理させる関数
function binarySearchImpl(
  arr: number[],
  target: number,
  left: number,
  right: number
): number {
  // targetが存在しない場合は即時return
  if (left > right) {
    return -1;
  }

  // 探索配列の中間のindex
  const mid = Math.floor((left + right) / 2);

  if (target < arr[mid]) {
    // 探索配列の中間の要素よりtargetが小さい場合、探索配列の右端を変更して、binarySearchImplに渡す。
    // 次回の処理では今回の探索配列の左半分を探索する
    return binarySearchImpl(arr, target, left, mid - 1);
  }

  if (target > arr[mid]) {
    // 探索配列の中間の要素よりtargetが大きい場合、探索配列の左端を変更して、binarySearchImplに渡す。
    // 次回の処理では今回の探索配列の右半分を探索する
    return binarySearchImpl(arr, target, mid + 1, right);
  }

  //  targetがarrの中にない場合は、-1を返す
  return mid;
}

console.log(binarySearch([1, 5, 6, 10], 5)); // 1
console.log(binarySearch([1, 5, 6, 6, 6, 10], 6)); // 2
console.log(binarySearch([-1, 0, 2, 5, 6, 8, 9, 10], 0)); //1

最後に

手を動かして実装すると理解が深まりますね。

TypeScriptでBinary Search(二分探索)を実装してみる

Binary Searchとは？

TypeScriptでの実装

最後に

参考

Discussion