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;}