二分探索

問題を理解する

ソートされた整数の配列と対象の整数が与えられた場合、二分探索アルゴリズムを使用して対象の整数が配列内にあるかどうかを調べる関数を作成するよう求められます.ターゲットが配列内にある場合、関数はそのインデックスを返す必要があります.それ以外の場合は -1 を返します.

アプローチ 1: 反復

二分探索アルゴリズムは、ソートされた値のリストを半分に分割し、目的の値が見つかるまで検索スペースを絞り込み続けます.現在の検索空間を追跡する 2 つのポインター left と right を維持します.最初は、検索スペースはリスト全体です. 2 つのポインターを使用して中間値を見つけ、それを検索対象と比較します.中間値が目標値と等しい場合、目標値が見つかりました.中央の値がターゲットよりも大きい場合は、リストがソートされ、中央の値の後に来るすべての値が中央の値よりも大きくなければならないため、ターゲットの値が検索スペースの右半分に収まらないことを意味します.ターゲットよりもさらに大きいので、右半分全体を削除して、検索スペースを左半分に絞り込むことができます.中間値がターゲットよりも小さい場合は、左半分全体を削除して、右半分でターゲット値を検索できます.ターゲット値が見つかるか、検索スペースが使い果たされるまで、プロセスを繰り返します.

実装

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

  while (left <= right) {
    // Avoid overflow
    const mid = left + Math.floor((right - left) / 2);

    if (target === array[mid]) return mid;

    if (target < array[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

複雑性分析

時間の複雑さ: O(log(n))、n は入力配列内の整数の数です.

スペースの複雑さ: O(1).

アプローチ 2: 再帰的

入力配列、検索ターゲット、および 2 つのポインター left と right をパラメーターとして受け取る再帰関数を定義します. 2 つのポインターを使用して中央の値を見つけ、残りの半分で再帰関数を呼び出します.再帰は、ターゲットが見つかるか、left ポインターが right ポインターを超えると停止します.

実装

function binarySearch(array, target) {
  return binarySearchRecursive(array, target, 0, array.length - 1);
}

function binarySearchRecursive(array, target, left, right) {
  if (left > right) return -1;

  // Avoid overflow
  const mid = left + Math.floor((right - left) / 2);

  if (target === array[mid]) return mid;

  if (target < array[mid]) {
    return binarySearchRecursive(array, target, left, mid - 1);
  } else {
    return binarySearchRecursive(array, target, mid + 1, right);
  }
}

複雑性分析

時間の複雑さ: O(log(n))、n は入力配列内の整数の数です.

スペースの複雑さ: 再帰スタックを保持するための O(log(n)).

フォローして、定期的な更新を入手してください.次の投稿でお会いしましょう.

Github リポジトリ: daily-problem-solving-js

リファレンス: pinglu85