演習: 探索アルゴリズム

7-a. 線形探索を書く

以下の配列から、値 "ぶどう" のインデックスを返す関数 findFruit を作成してください。見つからない場合は -1 を返します。

const fruits = ["りんご", "みかん", "ぶどう", "もも", "いちご"];

console.log(findFruit(fruits, "ぶどう"));
console.log(findFruit(fruits, "バナナ"));

出力例:

2
-1

ヒント

本文 2-3 の linearSearch と同じ構造です。

7-b. 条件を変えた線形探索

配列を受け取り、最初に見つかった 80 点以上のスコアのインデックスを返す関数 findFirstHigh を作成してください。見つからない場合は -1 を返します。

console.log(findFirstHigh([65, 72, 85, 90, 55]));
console.log(findFirstHigh([30, 40, 50]));

出力例:

2
-1

ヒント

本文 2-4 の findFirstEven と同じパターンです。条件を変えてみてください。

7-c. 二分探索のトレース

以下のソート済み配列に対して binarySearch(data, 15) を実行したとき、各ループでの low、high、mid、arr[mid] の値を表に書き出してください。

const data = [5, 10, 15, 20, 25, 30, 35, 40, 45];

ヒント

最初は low = 0、high = 8 です。mid を計算して arr[mid] と 15 を比較し、探索範囲を絞っていきます。

7-d. 二分探索のトレース（見つからない場合）

7-c と同じ配列に対して binarySearch(data, 12) を実行したとき、各ループでの low、high、mid、arr[mid] の値を表に書き出してください。最終的に何が返されるかも答えてください。

const data = [5, 10, 15, 20, 25, 30, 35, 40, 45];

ヒント

12 は 10 と 15 の間にあるはずですが、配列には存在しません。low > high になるまで範囲が絞られていく過程を追ってください。

7-e. 穴埋め: 二分探索

二分探索で、目的の値が中央の値より大きい場合の処理が抜けています。/* ??? */ に入るコードを、選択肢から選んでください。

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      /* ??? */
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

選択肢:

(ア) low = mid
(イ) low = mid + 1
(ウ) low = mid - 1
(エ) high = mid + 1

ヒント

arr[mid] < target ということは、目的の値は mid より右にあります。mid 自体は既に調べたので、探索範囲の左端をどこに移動すべきか考えてください。(ア) を選ぶと mid を再度調べることになり、無限ループの原因になります。

7-f. 穴埋め: 二分探索のループ条件

以下の二分探索では、while のループ条件が抜けています。/* ??? */ に入るコードを、選択肢から選んでください。

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (/* ??? */) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

選択肢:

(ア) low < high
(イ) low <= high
(ウ) low > high
(エ) low !== high

ヒント

配列 [10, 20, 30] で 30 を探す場合を考えてください。1 回目のループで mid = 1、arr[1] = 20 なので low = 2 に更新されます。このとき low = high = 2 となり、arr[2] = 30 を調べれば見つかります。どの条件式なら、low と high が等しくなった状態でもループが続きますか。

7-g. 線形探索の比較回数

以下のコードについて、linearSearch(data, 43) を呼び出したとき、if の比較は何回実行されるか予測してください。予測した後、実行して確認してください。

function linearSearch(arr, target) {
  let count = 0;

  for (let i = 0; i < arr.length; i++) {
    count++;
    if (arr[i] === target) {
      console.log("比較回数: " + count);
      return i;
    }
  }

  console.log("比較回数: " + count);
  return -1;
}

const data = [34, 72, 15, 88, 43];

linearSearch(data, 43);
linearSearch(data, 99);

ヒント

43 は配列の何番目にありますか。先頭から順に比較するので、その位置 + 1 が比較回数です。99 は配列に存在しないので、全要素を比較します。

7-h. 探索回数の比較

要素数 16 のソート済み配列があります。線形探索と二分探索それぞれで、最悪の場合の比較回数は何回ですか。

ヒント

線形探索は全要素を調べます。二分探索は毎回範囲を半分にします。16 → 8 → 4 → 2 → 1 と何回で 1 になるか数えてください。

7-i. 隣接する同じ値

配列を受け取り、隣り合う 2 つの要素が同じ値になっている最初のインデックスを返す関数 findAdjacentDuplicate を作成してください。見つからない場合は -1 を返します。

console.log(findAdjacentDuplicate([1, 2, 3, 3, 4, 5]));
console.log(findAdjacentDuplicate([7, 2, 2, 8, 8]));
console.log(findAdjacentDuplicate([1, 2, 3, 4]));

出力例:

2
1
-1

ヒント

線形探索の応用です。arr[i] と arr[i + 1] を比較します。最後の要素には「次の要素」が存在しないので、ループの終了条件を i < arr.length - 1 にしてください。

発展: 疑似言語

FE（基本情報技術者試験）の科目 B では、JavaScript ではなく 疑似言語 でプログラムが出題されます。ここでは、JS で理解したアルゴリズムを疑似言語で読む練習をします。

JS の書き方	疑似言語の書き方
`let x = 0`	`整数型: x ← 0`
`arr[i]`	`Arr[i]`（添字は 1 から始まる）
`arr.length`	`要素数(Arr)`
`if (条件) { ... }`	`if (条件)` … `endif`
`while (条件) { ... }`	`while (条件)` … `endwhile`
`for (let i = 1; i <= n; i++)`	`for (iを1からnまで1ずつ増やす)` … `endfor`
`function f(x) { return y }`	`○整数型: f(整数型: x)` … `return y`
`//` コメント	`/` コメント `/`

7-j. 疑似言語で線形探索を読む

以下の疑似言語プログラムは、本文で学んだ線形探索を疑似言語で書いたものです。配列 Data が {34, 72, 15, 88, 43} で target が 88 のとき、戻り値はいくつになりますか。

○整数型: linearSearch(整数型の配列: Data, 整数型: target)
  整数型: i
  for (iを1から要素数(Data)まで1ずつ増やす)
    if (Data[i] = target)
      return i
    endif
  endfor
  return -1

ヒント

添字が 1 から始まることに注意してください。Data[1] が 34、Data[2] が 72、…です。88 は何番目ですか。

7-k. 疑似言語の代入と比較

以下の疑似言語プログラムは、配列 Data の全要素の合計を求める関数です。/* ??? */ に入るコードを、選択肢から選んでください。

○整数型: calcTotal(整数型の配列: Data)
  整数型: total ← 0
  整数型: i
  for (iを1から要素数(Data)まで1ずつ増やす)
    /* ??? */
  endfor
  return total

選択肢:

(ア) total = total + Data[i]
(イ) total ← total + Data[i]
(ウ) Data[i] ← total + Data[i]
(エ) total + Data[i]

ヒント

疑似言語では代入に ← を使います。= は比較（JS の === に相当）を表すので、代入には使えません。更新したい変数がどちらかにも注意してください。

7-l. 疑似言語で二分探索のトレース

以下の疑似言語プログラムについて、配列 Data が {10, 20, 30, 40, 50} で target が 40 のとき、各ループでの low、high、mid、Data[mid] の値を表に書き出してください。

○整数型: binarySearch(整数型の配列: Data, 整数型: target)
  整数型: low ← 1
  整数型: high ← 要素数(Data)
  整数型: mid

  while (low ≦ high)
    mid ← (low + high) ÷ 2 の商
    if (Data[mid] = target)
      return mid
    elseif (Data[mid] < target)
      low ← mid + 1
    else
      high ← mid - 1
    endif
  endwhile
  return -1

ヒント

low = 1、high = 5 から始まります。mid = (1 + 5) ÷ 2 = 3、Data[3] = 30 です。40 > 30 なので low を更新します。