概要

配列の中から特定の値を探し、最初に見つかった位置を求める線形探索の問題です。

考察

この問題では、\(N\) 冊の本の中から管理番号が \(K\) である本を探します。

重要な気づき

1. 最も小さい位置を求める: 管理番号 \(K\) の本が複数存在する可能性があるため、最初に見つかった位置を答える必要があります
2. 存在しない場合の処理: 見つからなかった場合は \(-1\) を出力します

素朴なアプローチで十分か？

本棚の本を左から順番に1冊ずつ確認していく方法（線形探索）を考えます。

• 最悪の場合、\(N\) 冊すべてを確認する必要があります
• \(N \leq 2 \times 10^5\) なので、\(O(N)\) の計算量で十分間に合います

この問題では、配列がソートされていないため、二分探索などの高速な手法は使えません。単純に先頭から順に探索するのが適切です。

具体例

例えば、\(N = 5\)、\(K = 3\)、\(A = [1, 3, 5, 3, 2]\) の場合： - \(A_1 = 1 \neq 3\) - \(A_2 = 3 = K\) → 見つかった！位置は 2

最初に見つかった時点で探索を終了し、答えは \(2\) となります。

アルゴリズム

1. 配列 \(A\) の先頭から順番に要素を確認する
2. \(A_i = K\) となる \(i\) が見つかったら、その位置 \(i + 1\)（1-indexed）を記録して探索を終了する
3. 最後まで見つからなければ \(-1\) を出力する

result = -1
for i = 0 to N-1:
    if A[i] == K:
        result = i + 1
        break
print(result)

計算量

• 時間計算量: \(O(N)\)
  • 最悪の場合、配列のすべての要素を1回ずつ確認します
• 空間計算量: \(O(N)\)
  • 入力の配列 \(A\) を保存するために必要です

実装のポイント

1. 1-indexed と 0-indexed の変換: 問題では「左から何番目か」を1から数えますが、プログラムの配列は0から始まるため、出力時に i + 1 とする必要があります

2. break文の使用: 最も小さい位置を求めるため、最初に見つかった時点で break してループを抜けます。これを忘れると、最後に見つかった位置が出力されてしまいます

3. 初期値の設定: result = -1 と初期化しておくことで、見つからなかった場合の処理を簡潔に書けます

   ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))

result = -1
for i in range(N):
    if A[i] == K:
        result = i + 1
        break

print(result)

---

この解説は claude4.5opus によって生成されました。