第二の巻 線形探索

初段 / 目安 15分

師範が二つめの巻物を開きます。「会員番号の帳簿から、目当ての番号を探せ。見つけた位置と、何回比べたかも報告せよ」

「何回比べたか」まで求められるのが、この巻物の妙なところです。答えが合っていればよいのではなく、そこにたどり着くまでに何手かかったかを自分で数えさせる。師範がわざわざそう書いたのには理由がありますが、それは第四の巻まで伏せておきます。

帳簿は先頭から順に並んでいます。あなたのやることは、人が指で追うのと同じです。1件見て、違ったら次を見る。それだけです。

完成条件

会員番号の配列と、探したい番号を受け取り、見つけた位置と比較回数を1つの文字列にして返す関数 linearSearch を作ってください。どの言語で解く場合も、関数名は linearSearch にしてください。

返す文字列の形は次のとおりです。位置は先頭を 0 とする番号です。

位置 3 / 比較 4回

• 最後まで見つからなかったときは、位置を -1 にします。比較回数は最後まで数えた回数です
• 「位置」「/」「比較」「回」の前後の半角スペースまで一致させること
• 配列には必ず1つ以上の要素が入っています

数え方の約束

比較回数は、帳簿の1件と目当ての番号を照らし合わせた回数です。1件目を見た時点で 1 回、2件目を見た時点で 2 回になります。見つけたらそこで打ち切り、それ以降は数えません。

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

見つけたあとも配列の最後までループを回してしまうと、比較回数が合いません。見つけた瞬間に打ち切る書き方を、自分の言語で確かめてから始めてください。

添字と途中終了

[0, 7, 4] の添字は 0, 1, 2、その位置の値は 0, 7, 4 です。Python の range(3) は 0 から 2 まで、range(1, 3) は 1 と 2 を作り、終点 3 は含めません。Java などの i++ は i を 1 増やします。等しいかの比較は Python と Java が ==、JavaScript と TypeScript が === です。代入の = とは役割が違います。

別の題材として、最初の正の温度を返す関数を見ます。return はループだけでなく関数全体をその場で終了します。引数は渡された値を受け取る変数です。関数を呼ぶには firstWarm(temperatures) のように括弧内に値を渡します。

Python

def firstWarm(temperatures):
    for i in range(len(temperatures)):
        if temperatures[i] > 0:
            return temperatures[i]
    return 0

JavaScript

function firstWarm(temperatures) {
  for (let i = 0; i < temperatures.length; i++) {
    if (temperatures[i] > 0) {
      return temperatures[i];
    }
  }
  return 0;
}

TypeScript

function firstWarm(temperatures: number[]): number {
  for (let i = 0; i < temperatures.length; i++) {
    if (temperatures[i] > 0) {
      return temperatures[i];
    }
  }
  return 0;
}

Java

static int firstWarm(int[] temperatures) {
    for (int i = 0; i < temperatures.length; i++) {
        if (temperatures[i] > 0) {
            return temperatures[i];
        }
    }
    return 0;
}

演習の searchReport(position, count) は文字列を整える完成済みの補助関数です。一致したときはこれを呼んだ結果を返します。見つからない場合の最後の行も完成済みです。書くのは添字のループ・計数・一致時の終了です。同じ番号が複数あれば最初の位置で終了します。

1. 関数名は linearSearch。どの言語で解く場合も同じ名前にすること
2. 先頭から順に1件ずつ照らし合わせること
3. 照らし合わせた回数を数え、見つけたらそこで打ち切ること
4. 見つからなかったときは位置を -1 にすること
5. 「位置 3 / 比較 4回」の形の文字列を1つ返すこと。印字ではなく return で返す
6. ひな形の補助処理と出力整形を使い、添字のループ、比較回数の加算、一致時の終了を書くこと
7. 入力配列は空ではないことが保証されます
8. 同じ番号が複数あるときは最初の位置を返すこと