BFE.devでのAI解答例 - JavaScript コーディング問題
48. 重複要素のある配列で特定要素の一番出現位置を返す

解法1: 線形探索 配列を先頭から順番に探索して、特定の整数が最初に現れるindexを返します。配列が昇順にソートされているため、見つかった最初のインデックスが返されます。 時間計算量はO(n)で、最悪の場合、すべての要素を一度調べる必要があります。

function findIndex(arr, num) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      return i;
    }
  }
  return -1;
}

解法2: 二分探索 配列が昇順にソートされているため、二分探索を使用して特定の整数を探します。私たちは、配列の中央の要素が特定の整数より大きいか小さいかを調べて、配列を半分に割ることができます。このプロセスを繰り返すと、特定の整数が見つかるか、配列を二分探索することができなくなるまで続けます。見つかった場合、そのインデックスを返します。見つからなかった場合、-1を返します。 時間計算量はO(log n)であり、配列が大きい場合でも高速に機能します。

function findIndex(arr, num) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] < num) {
      low = mid + 1;
    } else if (arr[mid] > num) {
      high = mid - 1;
    } else {
      // found it!
      return mid;
    }
  }
  // not found
  return -1;
}